.06 Теория графов. Лемма о рукопожатиях. Связность. Эйлеровость.

Представим себе граф, в котором вершины - это города, и 2 вершины соединены ребром, если два города, им соответствующие, соединены авиалинией.

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