Условие:
Какие утверждения верны?
(1) Если граф планарный, то его хроматическое число меньше пяти.
(2) Если в плоской укладке планарного графа граница хотя бы одной грани состоит из нечетного числа ребер, то граф не является двудольным.
(3) Если в графе есть полный подграф, то граф не может быть бихроматичным.
Ответ дайте в формате последовательности 0 и 1 (например, 001): на первом месте запишите 1, если утверждение (1) верное, в противном случае запишите 0; на втором месте 1, если утверждение (2) верное, в противном случае запишите 0; и т.д.
Решение:
Рассмотрим каждое утверждение по отдельности: 1. Утверждение (1): «Если граф планарный, то его хроматическое число меньше пяти». По теореме о красках для планарных графов (теорема о четырех красках) любой планарный граф раскрашивается не более чем в 4 цвета, а 4 5. Таким образом, хроматическое число действительно всегда меньше пяти. Вывод: утверждение (1) верно. 2. Утверждение (2): «Если в плоской укладке планарного графа граница хотя бы одной грани состоит из нечетного числа ребе...