8.2. Реберная связность

Реберная связность графа G — это минимальное число ребер, удаление которых из графа приводит к несвязному или тривиальному графу. Другими словами, — число ребер в разрезе с минимальным числом ребер. Например, для графа на рис. 8.4 реберная связность равна 2, поскольку удаление двух ребер делает граф несвязным, а удаление произвольного одного ребра не приводит к несвязному графу.

Рис. 8.4. 2-реберно-связный граф.

Граф G называется -реберно-связным, если Таким образом, чтобы сделать несвязным реберно-связный граф, необходимо удалить хотя бы k ребер.

Поскольку ребра, инцидентные любой вершине v графа G, образуют разрез, то

В следующей теореме мы связываем величины

Теорема 8.5. Для простого графа

Доказательство. Второе неравенство мы уже доказали. Первое неравенство можно доказать следующим образом:

Если G — несвязный граф, то . В этом случае условие выполняется.

Если G — связный граф и то граф G имеет мост .

Если мы удалим в этом случае одну из вершин, с которыми инцидентен мосте, то получится несвязный или тривиальный граф. Следовательно, и в этом случае условие к выполняется.

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

Таким образом, во всех случаях

Сейчас мы представим достаточные условия того, что равно Этот результат получен Чартрэндом [8.3].

Теорема 8.6. Пусть G — простой граф на вершинах. Если то

Доказательство. Можно показать, что G — связный граф (упражнение 1.14). Поэтому Так как теорема будет доказана, если мы покажем, что

Допустим, что Тогда существует такой разрез что . Пусть ребра из разреза инцидентны q вершинам множества вершинам множества

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

Если то во множествах имеются вершины, смежные только с вершинами множеств соответственно. Следовательно, каждое из множеств содержит по крайней мере по вершин. Таким образом, граф G содержит не менее вершин. Но что противоречит условию. Следовательно, не существует разреза 5 с