Задача на орграфы Докажите что в полном графе в котором более 4 вершин можно так ввести ориентацию рёбер что из любой вершины в любую другую будет существовать путь длины не более чем два

Предыдущий
вопрос Следующий
вопрос

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

Пусть у нас есть полный орграф с n вершинами, где n > 4. Рассмотрим произвольные две вершины u и v. Так как граф полный, существует направленное ребро из u в v и из v в u. Уберем данные ребра и рассмотрим остальные n-2 вершины.

Существует вершина w, которая не является ни u, ни v. Посмотрим на вершины, не смежные с w. Их остается n-3. Так как n > 4, остается как минимум еще одна вершина x, которая не смежна с w.

Теперь добавим ориентированные ребра u -> w, w -> x, x -> v. Теперь из любой вершины можно добраться до любой другой за не более чем два шага:

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