Связность и связные подграфы (клики)

Докажем более сильное утверждение, разрешим наличие в графе кратных рёбер (но без петель). Будем доказывать индукцией по количеству вершин. База для очевидна. Рассмотрим граф на двух вершинах и Чтобы он удовлетворил условию, необходимо, чтобы было хотя бы два кратных ребра Тогда одно из них ориентируем в а другое — в

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

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