Снова графы, ня.

[Sirion]

Пусть у нас есть связный граф на n вершинах. Найти минимальное k=k(n) такое, что независимо от конфигурации этого графа мы можем добавить в него не более k рёбер так, чтобы каждая его вершина содержалась в некотором цикле? Кратные рёбра и петли традиционно запрещены.

[zhekas]

[n/2]

[iPhonograph]

жекас, а для n=2 тоже ?

кратные рёбра запрещены, НЯ !

[Sirion]

да, пожалуй, стоит оговорить, что n больше всякого чётного простого числа)