Комбинаторика на ЮМШ

1) Рассмотрим красный шестиугольник и концентрический синий шестиугольник внутри него. Соединим соответственные вершины синими ребрами.

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

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

4) Размыкаем синее рёбер в точке пересечения с красным, получаем две точки, соединим их какой-нибудь выпуклой красной кривой, поставим на ней пять точек и отметим "внутри"ещё две точки. Точки на кривой соединяем красными ребрами, а "внутрение"точки друг с другом синими. Осталось из внутренних провести два синих ребра, для этого соединим их точками с кривой.