Существует ли граф на 9 вершинах, степени которых равны 1, 1, 1, 1, 1, 2, 4, 5, 6?

Рассмотрим вершину степени 6. Она соединена хотя бы с 3-я вершинами степени 1 (т.к. есть только
4 вершины степени больше 1). Аналогично вершина 5 соединена хотя бы с 2-я вершинами степени 1,
вершина 4 соединена хотя бы с 1 вершиной степени 1. Получим, что вершин степени 1 должно быть
хотя бы 3 + 2 + 1 = 6, но их только 5 – противоречие. Тогда такого графа не существует.


info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp