|
Рассмотрим граф из N вершин, каждая из которых соответствует паре человек-велосипед, им купленный. Вершина A соединена направленной дугой с B, если человек A ездил на велосипеде B. По условию, в каждую вершину входит ровно 2 дуги. Кроме того, если из вершины K выходят дуги к X, Y, то X и Y должны иметь общего потомка (назовем его Z). Заметим, что разным {X, Y} соответсвтуют разные Z, поскольку других предков, кроме X и Y, у Z нет.
Далее, пусть число выходящих дуг из K равно d > 2. Тогда каждой паре потомков K (X, Y) соответствуют различные Z. Следовательно, из каждого потомка выходит не менее 2-ч дуг. Теперь вместо потомков перейдем к рассмотрению вершин ранга r (длина минимального пути из K равна r). Индукцией по r несложно доказывается, что вершин ранга r не менее 3-х, и степень каждой из них не менее 2-x.
Если рассмотреть подграф G(K) - достижимые из K вершины, которых будет, скажем, m, то можно заметить следующее: из каждой вершины выходит не менее 2-х дуг, а из K - не менее 3-х, значит всего ребер не менее 2m+1. С другой стороны, в каждую вершину входит не более 2-х дуг, значит, ребер не более 2m. Противоречие.
Таким образом, из каждой вершины выходит не более 2-х дуг. А т.к. входит ровно две, то и выходит - тоже ровно две (посчитаем общее число ребер как выше). Пример такого графа оставляется как несложное упражнение читателю : )))
|
