Дано: граф.
Найти: доказать, что в любом графе найдутся по крайней мере две вершины одинаковой степени.
Решение:
Предположим, что все вершины графа имеют различные степени. Пусть минимальная степень равна d_min, а максимальная степень равна d_max.
Тогда у нас есть d_min вершин степени d_min и d_max вершин степени d_max. Всего у нас N вершин в графе.
Если d_min = d_max, то у нас уже есть две вершины одинаковой степени.
Если d_min < d_max, то количество вершин с различными степенями больше чем N, что противоречит количеству вершин в графе.
Таким образом, в любом графе будут как минимум две вершины с одинаковой степенью.
Ответ:
Таким образом, можно утверждать, что в любом графе найдутся по меньшей мере две вершины одинаковой степени.