Неориентированные графы

[provincialka]

(Оффтоп)

VAL в сообщении #785234 писал(а):

Вы спрашивали? Я спрашивал. Хотя ответ очевиден... Правильно! Нарисую картинку и отсканирую".

Правда, что ли? Кошмар! На всякий случай спросила у отпрыска, я такие неясности на нем проверяю (7 класс, он как раз в субботу был на кружке в универе, где про графы рассказывали). Конечно, сказал про точки и линии. Но про компьютер ответил правильно, что радует.

[germ9c]

такое доказательство подойдет?

Пусть у графа N вершин. Их степени могут быть числами 0, 1, N-1 (всего N вариантов) Предположим, что вершин с одинаковыми степенями нет. Тогда очевидно, что есть вершина A со степенью 0 (изолированная) и вершина B со степенью N-1 (инцидентная всем остальным, в том числе и вершине A). Но вершина A не может быть никому инцидентна. Противоречие.

[provincialka]

Верно.

Есть еще классическая задача про графы. Собрались шесть человек, некоторые из них дружат друг с другом. Доказать, что обязательно найдется либо три человека, которые попарно дружат, либо три, которые попарно не дружат.