MathDB

4

Part of 2020 Iranian Combinatorics Olympiad

Problems(1)

Finding a Star of Equal Degrees

Source: Iranian Combinatorics Olympiad P4

4/25/2020
Given a graph with 9999 vertices and degrees in {81,82,…,90}\{81,82,\dots,90\}, prove that there exist 1010 vertices of this graph with equal degrees and a common neighbour.
Proposed by Alireza Alipour
combinatoricsgraph theorygraph