Разделы 
Дополнительно
Задача по математике - 13294
2023-08-14 
Допустим, что с помощью некоторой триангуляции мы разбили сферу на «страны». Здесь под триангуляцией мы понимаем такое разбиение сферы, при котором каждая получившаяся «страна» граничит (то есть имеет общий участок границы ненулевой длины) ровно с тремя остальными «странами». Вершину графа, состоящего из граничных линий, мы назовем четной или нечетной, если из нее выходит соответственно четное или нечетное число таких линий. Можно ли построить такую триангуляцию сферы, при которой получились бы ровно две нечетные вершины, причем эти вершины оказались бы смежными?
Решение:
Допустим, что такая триангуляция осуществима с помощью графа $G$. Если мы удалим линию, соединяющую две нечетные вершины (при этом образуется одна «страна», граничащая с четырьмя другими «странами»), то получится новый граф $G^{ \prime}$, у которого все вершины окажутся четными. Поэтому мы сможем окрасить «страны» $G^{ \prime}$ в два цвета (скажем, красный и черный) так, чтобы граничащие между собой «страны» были окрашены в разные цвета. Пусть $r$ и $b$ обозначают число «стран» графа $G^{ \prime}$, окрашенных соответственно в красный и черный цвета. Мы можем предположить без ограничения общности, что единственная «страна», граничащая с четырьмя «странами», окрашена в красный цвет. Поскольку каждая из оставшихся «стран» граничит с тремя другими, $b = \frac{4 + (r - 1)3}{3}$. Однако это число не будет целым ни при каком $r$. Следовательно, искомой триангуляции не существует.
Допустим, что с помощью некоторой триангуляции мы разбили сферу на «страны». Здесь под триангуляцией мы понимаем такое разбиение сферы, при котором каждая получившаяся «страна» граничит (то есть имеет общий участок границы ненулевой длины) ровно с тремя остальными «странами». Вершину графа, состоящего из граничных линий, мы назовем четной или нечетной, если из нее выходит соответственно четное или нечетное число таких линий. Можно ли построить такую триангуляцию сферы, при которой получились бы ровно две нечетные вершины, причем эти вершины оказались бы смежными?
Решение:
Допустим, что такая триангуляция осуществима с помощью графа $G$. Если мы удалим линию, соединяющую две нечетные вершины (при этом образуется одна «страна», граничащая с четырьмя другими «странами»), то получится новый граф $G^{ \prime}$, у которого все вершины окажутся четными. Поэтому мы сможем окрасить «страны» $G^{ \prime}$ в два цвета (скажем, красный и черный) так, чтобы граничащие между собой «страны» были окрашены в разные цвета. Пусть $r$ и $b$ обозначают число «стран» графа $G^{ \prime}$, окрашенных соответственно в красный и черный цвета. Мы можем предположить без ограничения общности, что единственная «страна», граничащая с четырьмя «странами», окрашена в красный цвет. Поскольку каждая из оставшихся «стран» граничит с тремя другими, $b = \frac{4 + (r - 1)3}{3}$. Однако это число не будет целым ни при каком $r$. Следовательно, искомой триангуляции не существует.
