Саша нарисовал граф, в котором 55 вершин, некоторые из них попарно соединены ребрами. Докажите, что есть две вершины, из которых выходит одинаковое количество ребер (в том числе…

Чтобы доказать, что в графе с 55 вершинами найдутся хотя бы две вершины с одинаковым количеством исходящих рёбер, воспользуемся принципом pigeonhole (принципом голубятни).

1. Количество вершин: У нас есть 55 вершин.

2. Возможные степени вершин: Степень вершины в неориентированном графе (здесь рассматривается граф без направления рёбер) может принимать значения от 0 до 54. Это связано с тем, что одна вершина может быть соединена с другими 54 вершинами, но не с самой собой.

3. Количество разных значений степени: Таким образом, возможные значения для степени (количества исходящих рёбер) вершин будут от 0 до 54. Это означает, что всего есть 55 возможных значений степеней.

4. Применение принципа pigeonhole:

   • У нас есть 55 вершин.
   • Каждая из этих вершин может иметь степень от 0 до 54.
   • Однако, если хотя бы одна вершина имеет степень 54, это означает, что она соединена со всеми остальными вершинами. Но тогда ни одна другая вершина не сможет иметь степень 0, так как она уже соединена с этой вершиной. Это приводит к тому, что если одна вершина имеет степень 54, оставшиеся 54 вершины могут иметь степени от 0 до 53.

5. Заключение: Следовательно, 55 вершин действительно не могут иметь 55 различных степеней (если одна из вершин имеет максимальную степень 54, то другие должны занимать только 54 возможных степеней). Таким образом, согласно принципу pigeonhole, по крайней мере две вершины имеют одинаковое количество исходящих рёбер.

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