Дискретная математика: графы и автоматы. Альпин Ю.А - 15 стр.

§ 3. Деревья. Минимальные остовы графов                            15


получим несвязный граф с двумя компонентами. Пусть k — число
удалённых рёбер. Ясно, что k > 1. Обозначим через n1 и n2 количе-
ства вершин в компонентах полученного графа. По предположению
индукции первая компонента содержит не менее n1 − 1 рёбер, вторая
— не менее n2 − 1 рёбер. Тогда исходный граф содержал рёбер не
менее, чем (n1 − 1) + (n2 − 1) + k = n − 2 + k > n − 1. ¤
   Теорема 1. Для графа с n вершинами следующие свойства эк-
вивалентны:
   1) граф связный и без циклов (то есть, дерево);
   2) граф связный и у него n − 1 рёбер;
   3) граф не содержит циклов и имеет n − 1 рёбер;
   4) для любых различных вершин u, v существует единственная
простая (u, v)-цепь;
   5) в графе нет циклов, но добавление любого ребра дает граф с
единственным циклом.
    Д о к а з а т е л ь с т в о. 1) ⇒ 2). Для малых n утверждение
очевидно. Предположим, что оно верно для графов с числом вершин,
меньшим n, и рассмотрим связный граф с n вершинами, не содержа-
щий циклов. Удалив из него произвольное ребро (u, v) (в силу предло-
жения 1 оно является мостом), получим граф с двумя компонентами,
в каждой из которых вершин меньше, чем n. По предположению ин-
дукции эти компоненты содержат, соответственно, n1 − 1 и n2 − 1
рёбер, где n1 и n2 — количества вершин в компонентах. Тогда общее
количество рёбер в исходном графе равно (n1 −1)+(n2 −1)+1 = n−1.
    2) ⇒ 3). Допустим, что граф содержит цикл. Тогда, удалив какое-
либо ребро этого цикла, получим связный граф с n − 2 рёбрами, что
противоречит предложению 2.
    3) ⇒ 4). Докажем сначала, что граф связный. Пусть у него k ком-
понент, содержащих n1 , . . . , nk вершин. Каждая компонента является
деревом и по импликации 1) ⇒ 2), доказанной выше, i-я компонента
содержит ni − 1 рёбер, значит, всего рёбер в графе
              (n1 − 1) + . . . + (nk − 1) = n − k = n − 1.
Следовательно, k = 1 и граф связный. Согласно лемме 1 §1 для лю-
бых неравных вершин u, v существует простая (u, v)-цепь, а её един-
ственность сразу следует из леммы 3 §1.
    4) ⇒ 5). В графе нет циклов, поскольку наличие цикла по лем-
ме 2 влечёт и наличие простого цикла, а в простом цикле любые две
вершины, очевидно, соединены двумя простыми цепями. Легко так-
же видеть, что добавление любого нового ребра дает простой цикл.