Задача 019 — Задачи на Графы

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

Подсказка

Предположите противное. Докажите, что нет встречных рёбер. Затем попробуйте стягивать рёбра.

Решение

Будем доказывать индукцией по числу $n$ вершин. База для $n=3$ и $n=4$ проверяется без труда. Пусть для всех графов с менее чем $n$ вершинами условие выполнено, а в графе $G$ с $n$ вершинами и исходящими степенями 3 не нашлось двух непересекающихся циклов.

Предположим, что в $G$ есть встречные ребра между вершинами $v$ и $w$ . Тогда в $G$ есть цикл $v w$ , и в $G-\{v, w\}$ есть цикл, так как в нем из каждой вершины выходит хотя бы одно ребро. Следовательно, в $G$ нет встречных ребер.

Предположим, что в $G$ есть ребро $u v$ такое, что ни из какой вершины $x \in V(G)$ не выходят ребра в обе вершины $u$ и $v$ . Тогда стянем ребро $u v$ : удалим в $G$ вершины $u$ и $v$ и добавим новую вершину $w$ , в которую входят ребра из тех вершин, из которых входили ребра в $u$ и $v$ , и выходят ребра в те вершины, в которые выходили ребра из $v$ . Обозначим полученный граф через $G^{\prime}$ . В $G^{\prime} n-1$ вершина и степень каждой вершины равна 3 , поэтому для него выполнено индукционное предположение. Но тогда и в $G$ есть два непересекающихся цикла, так как если цикл в $G^{\prime}$ проходил через $w$ , то в $G$ этот проход можно заменить на проход через $v$ или $u v$ .

Осталось разобрать случай, когда каждое ребро имеет «предка», то есть вершину, из которой выходят ребра в оба конца этого ребра. Пусть $v$ — вершина наименьшей входящей степени (обозначим эту степень $d^{-}(v)$ ). Очевидно, $d^{-}(v) \leq 3$ .

(1) $d^{-}(v)=0$ . Тогда ребро, исходящее из $v$ , не имеет предка.
(2) $d^{-}(v)=1$ . Тогда ребро, входящее в $v$ , не имеет предка.
(3) $d^{-}(v)=2$ . Пусть есть ребра $u v$ и $w v$ . Тогда $u$ должно быть предком для $w v$ , а $w$ — для $u v$ , но тогда есть ребра $v w$ и $w v$ , а этот случай мы уже разобрали.
(4) $d^{-}(v)=3$ . Тогда все вершины имеют входящую степень 3. Пусть в вершину $x$ входят ребра $u x, v x, w x$ . Предком каждого из этих ребер должна быть $u, v$ или $w$ . Тогда в индуцированном подграфе на вершинах $u, v, w$ в каждую вершину входит хотя бы одно ребро, а так как в $G$ нет встречных ребер, вершины $u, v, w$ образуют цикл длины 3. Заметим, что вершины, в которые ведут ребра из $x$ , также образуют цикл длины 3 (так как мы можем обратить все ребра и повторить те же рассуждения). $B G$ нет встречных ребер, поэтому мы нашли два непересекающихся цикла.