Граф. Содержит ли граф цикл?

[NL0]

Допустим есть связный граф с $n$ вершинами. Сколько должен иметь ребер граф, чтобы он гарантированно содержал цикл?

Попробую разобраться:

1) Ясно, что $n-1$ ребра не хватит, потому как если просто выстроить в линию все $n$ вершин, то будет $n-1$ ребро без циклов.

2) Пусть граф представляет собой дерево из $n$ вершин и $n-1$ ребра их соединяющих (ведь только $n-1$ ребро сможет образовать дерево). Тогда добавив одно ребро мы гарантированно получим цикл, потому как изначально в дереве можно приехать из одной вершины в любую другую, а коли так, то добавление нового ребра проложит второй путь в эту вершину, а значит граф будет содержать цикл.

Таким образом необходимо не менее $n$ ребер в связном графе из $n$ вершин, для того, чтобы он имел цикл. Верны ли рассуждения?

[mihaild]

Идея правильная, расписана вторая часть недостаточно четко. Да, добавление ребра к дереву создает в нем цикл. Ну и что? (например, далеко не любой граф получается добавлением одного ребра к дереву)

[NL0]

mihaild в сообщении #1197463 писал(а):

Идея правильная, расписана вторая часть недостаточно четко. Да, добавление ребра к дереву создает в нем цикл. Ну и что? (например, далеко не любой граф получается добавлением одного ребра к дереву)

Спасибо! Вы имеете ввиду, что я не рассмотрел случай, когда граф изначально был с циклами?))

[mihaild]

Строго говоря, вообще не было никакого "изначально". У вас просто есть граф с более чем $n - 1$ ребром, и надо доказать, что в нем есть цикл.
Это можно сделать, например, так. Взять какое-нибудь ребро в этом графе, рассмотреть граф без этого ребра (в нем не менее чем $n - 1$ ребро) и доказать, что если к любому графу, в котором есть хотя бы $n - 1$ ребро, добавить ребро, то получится граф, в котором есть цикл.