Задачи на графы Докажите, что в любом графе найдутся по крайней мере две вершины одинаковой степени.

Предыдущий
вопрос Следующий
вопрос

Доказательство:

Предположим, что все вершины графа имеют различные степени. Тогда максимальная степень вершины равна n-1, где n - количество вершин в графе. Так как степени вершин могут быть только целыми числами от 0 до n-1, а у нас n вершин, то как минимум две вершины должны иметь одинаковую степень.

Таким образом, мы доказали, что в любом графе найдутся по крайней мере две вершины одинаковой степени.