Связность графов

Свойства графов:

1°. Каждая вершина графа входит в одну и только в одну компоненту связности.

2°. Любой конечный граф имеет конечное число компонент связности.

3°. Граф, состоящий из единственной компоненты связности, является связным.

4°. Каждая компонента связности графа является его подграфом.

5°. Для любого графа либо он сам, либо его дополнение является связным.

Доказательства свойств

§4. Новые определения

Маршрутом в данном графе G называется конечная последовательность ребер вида

{v₀,v₁},{v₁,v₂}, …, {v_m-1,v_m}

(обозначаемая также через (v₀> v₁> v₂> …> v_m) Очевидно следующее свойство маршрута: любые два последовательных ребра либо смежны, либо одинаковы. Но не всякая последовательность ребер, обладающая этим свойством, является маршрутом (в качестве примера рассмотрим звездный граф и возьмем его ребра в произвольном порядке). Каждому маршруту соответствует последовательность вершин v_о, v₁, ..., v_m; v₀ называется начальной вершиной, а v_m -- конечной вершиной маршрута. Таким образом, мы будем говорить о маршруте из v₀ в v_m. Заметим, что для любой вершины V^ тривиальным маршрутом, вообще не содержащим ребер, является маршрут из v₀ в v₀. Длиной маршрута называется число ребер в нем; например, на Рис. 1 маршрут v>w>x>y>z>z>y>w из v в w имеет длину, равную семи.

Маршрут называется цепью, если все его ребра различны, и простой цепью, если все вершины v₀, v₁ ..., v_m различны (кроме, может быть, v₀= v_m).

Рис 4.1

Цепь или простая цепь замкнуты, если v₀= v_m. Замкнутая простая цепь, содержащая по крайней мере одно ребро, называется циклом; в частности, любая петля или любая пара кратных ребер образует цикл.

Замечание. Маршрут, также называют путем, реберной последовательностью. Цепь называют путем, полупростым путем; простую цепь -- цепью, путем, дугой, простым путем, элементарной цепью; замкнутую цепь -- циклической цепью, контуром; цикл -- контуром, контурной цепью, простым циклом, элементарным циклом.

Чтобы разобраться в приведенных выше определениях, рассмотрим еще раз Рис. 1. Мы видим, что v>w>x>y>z>z>x -- цепь, v>w>x>y>z-- простая цепь, v>w>x>y>z>x>v -- замкнутая цепь и v>w>x>y>v-- цикл. Цикл длины три (например, v>w>x>v) называется треугольником.

Дадим теперь другое, быть может, более удобное определение связных графов. Граф G называется связным, если для любых двух его вершин v и w существует простая цепь из v в w. Любой граф можно разбить на непересекающиеся связные подграфы, называемые компонентами (связности), задав следующее отношение эквивалентности на множестве его вершин: две вершины эквивалентны (или связаны), если существует простая цепь из одной в другую. Оставим читателю доказательство того, что связанность вершин действительно является отношением эквивалентности и что вершины, принадлежащие одному классу эквивалентности, вместе с инцидентными им ребрами образуют компоненты (связности) графа. Очевидно, что связный граф состоит из одной компоненты. Граф называется несвязным, если число его компонент больше единицы. Докажем теперь, что данные здесь определения не противоречат определениям из § 3.

Теорема 5А. Граф является связным в смысле данного выше определения тогда и только тогда, когда он связен в смысле определения из §3.

Доказательство. => Пусть граф G связен в смысле определения из данного параграфа. Допустим, что G представляет собой объединение двух (непересекающихся) подграфов, а v и w -- вершины, принадлежащие разным подграфам. Любая простая цепь из v в w должна содержать ребро, инцидентное некоторым двум вершинам из разных подграфов; так как такого ребра не существует, получили противоречие.

<= Теперь предположим, что граф G связен в смысле определения из § 3 и не существует никакой простой цепи, связывающей заданную пару вершин v и w. Тогда, по данному выше определению компонент связности, вершины v и w будут принадлежать разным компонентам. Исходя из этого, можно представить G в виде объединения двух графов, одним из которых является компонента, содержащая v, а другим -- объединение оставшихся компонент. Отсюда и получаем нужное противоречие. //

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

Теорема 5В. Пусть G -- простой граф с n вершинами и k компонентами. Тогда число m его ребер удовлетворяет неравенствам

n -- k < m < (n -- k)(n -- k + 1)/2.

Доказательство. Неравенство m ? n -- k докажем индукцией по числу ребер в G. Если О -- вполне несвязный граф, то утверждение очевидно. Если в графе G число ребер минимально (скажем m₀), то удаление любого ребра должно привести к увеличению числа компонент на единицу. Таким образом, в получившемся графе будет n вершин, k + 1 компонент и m₀ -- 1 ребер. Следовательно, в силу индуктивного предположения m₀ -- 1 > n -- (k+1), откуда сразу же получается m₀ > n -- k, что и утверждалось.

Для доказательства оценки сверху можно считать каждую компоненту графа G полным графом. Предположим, что Сi и Сj -- две компоненты соответственно с n_i и n_j; вершинами и ni ? nj? 1. Если мы заменим Сi и Сj; на полные графы с n_i + 1 и n_j -- 1 вершинами, то общее число вершин не изменится, а число ребер увеличится на положительную величину

1/2{(n_i+1) n_i - n_i (n_i -1)}-1/2{ n_j (n_j -1)-( n_j -1)( n_j -2)} = n_i- n_j +1.

Следовательно, для того чтобы число ребер в графе G было максимально возможным (при заданных n и k), G должен состоять из k-- 1 изолированных вершин и полного графа с n -- k + 1 вершинами. Отсюда сразу вытекает нужное неравенство. //

Следствие 5С. Любой простой граф с т вершинами и более чем (n-- 1)(n -- 2)/2 ребрами связен. //

Другое направление исследования связных графов задается следующим вопросом: насколько сильно связен связный граф? Этот вопрос можно сформулировать и так: сколько ребер нужно удалить из графа, чтобы он перестал быть связным?

Рис. 2 Рис. 3

Для обсуждения данного вопроса удобно ввести еще два определения. Разделяющим множеством связного графа G называется такое множество его ребер, удаление которого приводит к несвязному графу. Например, в графе, изображенном на Рис. 2, каждое из множеств {е₁ ,е₂, е₅} и {е₃, е₆, е₇, е₈) является разделяющим; несвязный граф, оставшийся после удаления второго из этих множеств, показан на Рис. 3. Далее, назовем разрезом такое разделяющее множество, никакое собственное подмножество которого не является разделяющим. В рассмотренном выше примере разрезом будет только второе разделяющее множество. Легко видеть, что после удаления ребер, принадлежащих разрезу, остается граф, имеющий ровно две компоненты. Если разрез состоит из единственного ребра e, то е называется мостом, или перешейком (Рис. 4).

Все эти определения легко переносятся на несвязные графы. В произвольном графе G разделяющим множеством называется такое множество ребер, удаление которого увеличивает число компонент вG. Разрезом в G называется разделяющее множество, никакое собственное подмножество которого не является разделяющим. Заметим, что в результате удаления ребер, принадлежащих разрезу, число компонент в G увеличивается ровно на единицу.

§5. Эйлеровы графы

Связный граф G называется эйлеровым, если существует замкнутая цепь, проходящая через каждое его ребро; такая цепь называется эйлеровой цепью. Отметим, что в этом определении требуется, чтобы каждое ребро проходилось 1 только один раз.

1 2 3

Если снять ограничение на замкнутость цепи, то граф называется полуэйлеровым; при этом каждый эйлеров граф будет полуэйлеровым. На Рис. 1, 2 и 3 изображены соответственно не эйлеров, полуэйлеров и эйлеров графы. Заметим, что предположение о связности графа G введено только ради удобства, так как оно позволяет не рассматривать тривиальный случай графа, содержащего несколько изолированных вершин.

Название «эйлеров» возникло в связи с тем, что Эйлер первым решил знаменитую задачу о кёнигсбергских мостах, в которой нужно было узнать, имеет ли граф, изображенный на Рис. 4, эйлерову цепь (не имеет!).Сразу же возникает вопрос: можно ли найти необходимые и достаточные условия для того, чтобы граф был эйлеровым?

Лемма 6А. Если степень каждой вершины графа G не меньше двух, то G содержит цикл.

Доказательство. Если в графе G имеются петли или кратные ребра, то утверждение очевидно; поэтому предположим, что G является простым графом. Пусть v -- произвольная вершина графа G; построим по индукции маршрут v> v₁> v₂>…, выбирая вершину v₁ смежной вершине v, а для i ? 1 -- выбирая v_i+1 смежной v_i и отличной от v_i-1(существование такой вершины v_i+1 гарантировано условием леммы). Так как G имеет конечное число вершин, то в конце концов придем к вершине, которая уже была выбрана раньше. Предположим, что ад -- первая такая вершина; тогда часть маршрута, лежащая между двумя вхождениями v_k, и является требуемым циклом.

Рис 4

Теорема 6В. Связный граф G является эйлеровым тогда и только тогда, когда каждая вершина в G имеет четную степень.

Доказательство. => Предположим, что Р является эйлеровой цепью в графе G. Тогда при всяком прохождении цепи Р через любую из вершин графа степень этой вершины увеличивается на два. А так как каждое ребро встречается в Р ровно один раз, то каждая вершина должна иметь четную степень.

<= Проведем доказательство индукцией по числу ребер в G. В силу связности G, степень каждой вершины не меньше двух, а отсюда, по предыдущей лемме, заключаем, что граф G содержит цикл C. Если С проходит через каждое ребро графа G, то доказательство завершено; если нет, то, удаляя из G ребра, принадлежащие циклу С, получим новый (быть может, и несвязный) граф H. Число ребер в Н меньше, чем в G, и любая вершина в H по-прежнему имеет четную степень. Согласно индуктивному предположению, в каждой компоненте графа Н существует эйлерова цепь. В силу связности графа G, каждая компонента в Н имеет по крайней мере одну общую вершину с циклом С, поэтому искомую эйлерову цепь графа G можно получить так: идем по ребрам цикла С до тех пор, пока не встретим неизолированную вершину графа H, затем следуем по эйлеровой цепи той компоненты в H, которая содержит указанную вершину; далее продолжаем путь по ребрам цикла С, пока не встретим вершину, принадлежащую другой компоненте графа H, и т. д.; заканчивается процесс тогда, когда попадаем обратно в начальную вершину (см. Рис. 5).

Рис 5

Следствие 6С. Связный граф является эйлеровым тогда и только тогда, когда семейство его ребер можно разбить на непересекающиеся циклы. //

Следствие 6В. Связный граф является полуэйлеровым тогда и только тогда, когда в нем не более двух вершин имеют нечетные степени. //

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

Завершая рассмотрение эйлеровых графов, дадим алгоритм построения эйлеровой цепи в данном эйлеровом графе. Этот метод известен под названием алгоритма Флёри.

Теорема 6Е. Пусть G -- эйлеров граф; тогда следующая процедура всегда возможна и приводит к эйлеровой цепи графа G. Выходя из произвольной вершины и, идем по ребрам графа произвольным образом, соблюдая лишь следующие правила: (i) стираем ребра по мере их прохождения и стираем также изолированные вершины, которые при этом образуются; (ii) на каждом этапе идем по мосту только тогда, когда нет других возможностей.

Доказательство. Предположим, что достигли некоторой вершины v; тогда если v ? u, то оставшийся подграф Н связен и содержит ровно две вершины нечетной степени, а именно u и v. Согласно следствию 6D, граф H содержит полуэйлерову цепь Р из v и u. Поскольку удаление первого ребра цепи Р не нарушает связности графа H, отсюда следует, что описанное в теореме построение возможно на каждом этапе. Если же v = u, то доказательство остается тем же самым до тех пор, пока есть еще ребра, инцидентные вершине u.

Осталось только показать, что данная процедура всегда приводит к полной эйлеровой цепи. Но это очевидно, так как в G не может быть ребер, оставшихся непройденными после использования последнего ребра, инцидентного и (в противном случае удаление некоторого ребра, смежного одному из оставшихся, привело бы к несвязному графу, что противоречит (ii)).

§6. Гамильтоновы графы

Рис 1 Рис. 2

Рис. 3 Рис. 4

граф связанность цепь дерево

В предыдущем параграфе мы обсудили проблему существования замкнутой цепи, проходящей через каждое ребро заданного связного графа G. Можно рассмотреть аналогичную проблему существования замкнутой цепи, проходящей ровно один раз через каждую вершину графа G. Ясно, что такая цепь должна быть циклом (исключая тривиальный случай, когда G является графом N₁); если такой цикл существует, то он называется гамильтоновым циклом, а G называется гамильтоновым графом. Граф, который содержит простую цепь, проходящую через каждую его вершину, называется полугамильтоновым; заметим, что всякий гамильтонов граф является полугамильтоновым. На Рис. 1, 2 и 3 изображены соответственно не гамильтонов, полугамильтонов и гамильтонов графы.

Название «гамильтонов цикл» возникло в связи с тем, что сэр Уильям Гамильтон занимался исследованием существования таких циклов в графе, соответствующем додекаэдру; на Рис. 4 показан такой цикл (его ребра изображены сплошными линиями).

В теореме 6В получили необходимое и достаточное условие для того, чтобы связный граф был эйлеровым. Естественно было бы надеяться, что и для гамильтоновых графов удастся получить аналогичный критерий. Однако поиск такого критерия стал одной из главных нерешенных задач теории графов! О гамильтоновых графах в общем-то известно очень мало. Большинство известных теорем имеет вид: «если G имеет достаточное число ребер, то G является гамильтоновым графом»; вероятно, самой знаменитой из них является следующая теорема, принадлежащая Г. Э. Дираку и потому известная как теорема Дирака.

Теорема 7А (Дирак 1952). Если в простом графе с n (? 3) вершинами р(v) ? n/2 для любой вершины v, то граф G является гамильтоновым.

Замечание. Существует несколько доказательств этой широко известной теоремы; здесь приведем доказательство, принадлежащее Д. Дж. Ньюману.

Доказательство. Добавим к графу k новых вершин, соединяя каждую из них с каждой вершиной из G. Будем предполагать, что k -- наименьшее число вершин, нужных для того, чтобы полученный граф G' стал гамильтоновым. Затем, считая, что k > 0, придем к противоречию.

Пусть v>p>w>…>v-- гамильтонов цикл в G', где v и w -- вершины из G, а р -- одна из новых вершин. Тогда w не является смежной с v, так как в противном случае могли бы не использовать вершину р, что противоречит минимальности k. Более того, вершина (скажем w'), смежная вершине w, не может непосредственно следовать за вершиной v', смежной вершине v, потому что тогда могли бы заменить v>p>w>…>v'>w'>…>v на v>v'>…>w>w'>…> v, перевернув часть цикла, заключенную между w и v'. Отсюда следует, что число вершин графа G', не являющихся смежными с v, не меньше числа вершин, смежных с v (т. е. равно по меньшей мере n/2 + k); с другой стороны, очевидно, что число вершин графа G', смежных с w, тоже равно по меньшей мере n/2 + k. А так как ни одна вершина графа G' не может быть одновременно смежной и не смежной вершине w, то общее число вершин графа G', равное n +k, не меньше, чем n + 2k. Это и есть искомое противоречие. //

§7. Бесконечные графы

В этом параграфе покажу, как можно обобщить некоторые определения, данные в предыдущих параграфах, на случай бесконечных графов. Напомним читателю, что бесконечным графом называется пара (V(G), Е(G))> где V(G)-- бесконечное множество элементов, называемых вершинами, а Е(G) -- бесконечное семейство неупорядоченных пар элементов из V(G) у называемых ребрами. Если оба множества V(G) и Е(G) счетны, то G называется счетным графом. Заметим, что наши определения исключают те случаи, когда V(G) бесконечно, а Е(G) конечно (такие объекты являются всего лишь конечными графами с бесконечным множеством изолированных вершин), или когда Е(G) бесконечно, а V(G) конечно (такие объекты являются конечными графами с бесконечным числом петель или кратных ребер).

Рис. 1

Некоторые определения, данные в гл. 2 (таких понятий, как «смежный», «инцидентный», «изоморфный», «подграф», «объединение», «связный», «компонента»), сразу переносятся на бесконечные графы. Степенью вершины v бесконечного графа называется мощность множества ребер, инцидентных v степень вершины может быть конечной или бесконечной. Бесконечный граф, все вершины которого имеют конечные степени, называется локально конечным; хорошо известным примером такого графа является бесконечная квадратная решетка, часть которой изображена на Рис. 1. Аналогичным образом можно определить локально счетный бесконечный граф -- как граф, все вершины которого имеют счетную степень). Пользуясь этими определениями, докажем сейчас простой, но важный результат.

Теорема 8А. Каждый связный локально счетный бесконечный граф является счетным.

Доказательство. Пусть v -- произвольная вершина такого бесконечного графа, и пусть А₁ -- множество вершин, смежных v, A₂ -- множество всех вершин, смежных вершинам из А₁ и т. д. По условию теоремы А₁ -- счетно и, следовательно, множества A₂, A₃, ... тоже счетны (здесь используем тот факт, что объединение не более чем счетного множества счетных множеств счетно); следовательно, {v}, А₁, А₂,…-- последовательность множеств, объединение которых счетно. Кроме того, эта последовательность содержит каждую вершину бесконечного графа в силу его связности. Отсюда и следует нужный результат. //

Следствие 8В. Каждый связный локально конечный бесконечный граф является счетным. //

Помимо этого, на бесконечный граф G можно перенести понятие маршрута, причем тремя различными способами:

(i) конечный маршрут в G определяется так же, как и в §5;

(ii) бесконечным в одну сторону маршрутом в G (с начальной вершиной v₀,) называется бесконечная последовательность ребер вида {v₀, v₁}, {v₁, v₂}, ... ;

(iii) бесконечным в обе стороны маршрутом в G называется бесконечная последовательность ребер вида ..., {v_-2, v_-1 }, { v_-2, v₀}, { v₀, v₁},{ v₁, v₂} ,... .

Бесконечные в одну сторону и в обе стороны цепи и простые цепи определяются очевидным образом, так же как и понятия длины цепи и расстояния между вершинами. Следующий результат, известный как лемма Кёнига, говорит о том, что бесконечные простые цепи не так уж трудно обнаружить.

Теорема 8С (Кёниг 1936). Пусть G -- связный локально конечный бесконечный граф; тогда для любой его вершины v существует бесконечная в одну сторону простая цепь с начальной вершиной v.

Доказательство. Если z -- произвольная вершина графа G, отличная от v, то существует нетривиальная простая цепь от v до z; отсюда следует, что в G имеется бесконечно много простых цепей с начальной вершиной v. Поскольку степень v конечна, то бесконечное множество таких простых цепей должно начинаться с одного и того же ребра. Если таким ребром является {v, v₁}, то, повторяя эту процедуру для вершины v₁, получим новую вершину v₂ и соответствующее ей ребро {v₁, v₂}. Продолжая таким образом, получим бесконечную в одну сторону простую цепь v>v₁>v₂… .

Важное значение леммы Кёнига состоит в том, что она позволяет получать результаты о бесконечных графах из соответствующих результатов для конечных графов. Типичным примером этого является следующая теорема.

Теорема 8D. Пусть G -- счетный граф, каждый конечный подграф которого планарен; тогда и G планарен.

Доказательство. Так как G-- счетный граф, то его вершины можно занумеровать в последовательность v₁, v₂, v₃,.... Исходя из нее, построим строго возрастающую последовательность G₁ G₂ G₃ ... подграфов графа G, выбирая в качестве G_k подграф с вершинами v₁, ..., v_k и ребрами графа G, соединяющими только эти вершины между собой. Далее, примем на веру тот факт, что графы G_i могут быть уложены на плоскости конечным числом (скажем m(i)) топологически различных способов, и построим еще один бесконечный граф H. Его вершины w_ij (i?1, 1 ? j ? m(i)) пусть соответствуют различным укладкам графов {G_i}, а его ребра соединяют те из вершин w_ij и w_kl, для которых k = i + 1 и плоская укладка, соответствующая w_kl «расширяется» (очевидным образом) до укладки, соответствующей w_ij. Легко видеть, что граф H связен и локально конечен, поэтому, как следует из леммы Кёнига, он содержит бесконечную в одну сторону простую цепь. А так как граф G является счетным, то эта бесконечная простая цепь и дает требуемую плоскую укладку графа G. //

Стоит подчеркнуть, что если принять дальнейшие аксиомы теории множеств (в частности, аксиому выбора для несчетных множеств), то многие результаты (подобные только что доказанному) можно перенести и на такие бесконечные графы, которые не обязательно являются счетными.

В заключение этого небольшого отступления в область бесконечных графов дадим краткий обзор свойств бесконечных эйлеровых графов. Естественно назвать связный бесконечный граф (эйлеровым, если в нем существует бесконечная в обе стороны цепь, содержащая каждое ребро графа G; такая бесконечная цепь называется (двусторонней) эйлеровой цепью. Далее, назовем граф G полуэйлеровым, если в нем существует бесконечная (в одну или в обе стороны) цепь, содержащая каждое ребро графа G. Заметим, что эти определения требуют счетности графа G. В следующих теоремах даны условия, необходимые для того, чтобы бесконечный граф был эйлеровым или полуэйлеровым.

Теорема 8Е. Пусть G -- связный счетный граф, являющийся эйлеровым. Тогда (i) в графе G нет вершин нечетной степени; (ii) для каждого конечного подграфа Н графа G бесконечный граф Н (полученный удалением из G ребер графа Н) имеет не более двух бесконечных, связных компонент; (iii) если, кроме того, степень любой вершины из Н четна, то Н имеет ровно одну бесконечную связную компоненту.

Доказательство. (i) Предположим, что Р -- эйлерова цепь; тогда, рассуждая так же, как и в доказательстве теоремы 6В, получим, что степень любой вершины из G должна быть либо четной, либо бесконечной.

(ii) Разобьем цепь Р на три подцепи Р_, Р₀ и Р₊ так, что Р₀ -- конечная цепь, содержащая все ребра графа Н (и, быть может, другие ребра), а Р_- и Р₊ -- две бесконечные в одну сторону цепи. Тогда бесконечный граф /С, образованный ребрами цепей Р_ и Р₊(а также инцидентными им вершинами) имеет не более двух бесконечных компонент. Так как H получается из K присоединением лишь конечного множества ребер, то отсюда и следует нужный результат.

(iii) Пусть v и w -- начальная и конечная вершины цепи Р₀; v и w связаны в Н. Если v = w, то это очевидно; если v ?w, то, применяя следствие 6D к графу, полученному из Р₀ удалением ребер графа Н (по предположению в этом графе ровно две вершины, а именно v и w, имеют нечетные степени), получим требуемый результат. //

Можно получить соответствующие необходимые условия для полуэйлеровых бесконечных графов.

Теорема 8F. Пусть G -- связный счетный граф, являющийся полуэйлеровым, но не эйлеровым; тогда (i) G содержит либо не более одной вершины нечетной степени, либо не менее одной вершины бесконечной степени; (ii) для каждого конечного подграфа Н графа G бесконечный граф Н (описанный ранее) содержит ровно одну бесконечную компоненту. //

Теорема 8G. Пусть G-- связный счетный граф; G является эйлеровым графом тогда и только тогда, когда выполнены условия (i), (ii) и (iii) теоремы 8Е. Более того, G является полуэйлеровым тогда и только тогда, когда выполнены либо эти условия, либо условия (i) и (ii) теоремы 8F.

Глава 3. Деревья

§8. Элементарные свойства деревьев

Лесом называется граф, не содержащий циклов; связный лес называется деревом. Например, на Рис. 1 изображен лес, состоящий из четырех компонент, каждая из которых является деревом. Заметим, что по определению деревья и леса являются простыми графами.

Рис.1

По многим показателям дерево представляет собой простейший нетривиальный тип графа. Как будет показано в теореме 9А, оно обладает некоторыми «приятными» свойствами; например, любые две его вершины соединены единственной простой цепью. Пытаясь доказать какой-нибудь общий результат или проверить гипотезу для графов, удобно бывает начать с деревьев, хотя и существует несколько гипотез, которые еще не доказаны для произвольных графов, несмотря на то, что они верны для деревьев.

В следующей теореме перечислены некоторые простые свойства деревьев.

Теорема 9А. Пусть граф Т имеет n вершин. Тогда следующие утверждения эквивалентны: (i) Т является деревом, (ii) Т не содержит циклов и имеет n -- 1 ребер; (iii) Т связен и имеет n -- 1 ребер; (iv) Т связен и каждое его ребро является мостом; (v) любые две вершины графа Т соединены ровно одной простой цепъю; (vi) Т не содержит циклов, но, добавляя к нему любое новое ребро, получим ровно один цикл.

Доказательство. Если n = 1, утверждение очевидно. Предположим поэтому, что n? 2.

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

(ii) => (iii). Если граф Т несвязен, то каждая его компонента представляет собой связный граф без циклов. Из предыдущей части доказательства следует, что число вершин в каждой из компонент больше числа ее ребер на единицу. Значит, полное число вершин графа Т больше полного числа его ребер по крайней мере на 2, а это противоречит тому, что Т имеет n -- 1 ребер.