Given a graph with $99$ vertices and degrees in $\{81,82,\dots,90\}$, prove that there exist $10$ vertices of this graph with equal degrees and a common neighbour. Proposed by Alireza Alipour
Problem
Source: Iranian Combinatorics Olympiad P4
Tags: combinatorics, graph theory, graph
27.04.2020 16:27
It is impossible for every vertex to have degree $81$, because it would imply the sum of all degrees is odd. Suppose to the contrary that there doesn't exist such $10$ vertices. Let $v$ be a vertex with degree more than $81$. Consider $N(v)$, the set of neighbors of $v$. For each $k\in \{ 81,82,\dotsc , 89\}$, at most $9$ vertices of degree $k$ belong to $N(v)$. Since $|N(v)|>9\cdot 9$, there exists a vertex in $N(v)$ that has degree $90$. Call this vertex $w$. Consider $N(w)$, the set of neighbors of $w$. By a similar argument $N(w)$ must contain exactly $9$ vertices of degree $k$ for each $k\in \{ 81,82,\dotsc ,90\}$. Hence, there are at least $10$ vertices that have degree $90$. We claim that they constitute the desired $10$ vertices. For each vertex $u$ of the $10$ vertices, the number of vertices that are not neighbor of $u$ is equal to $9$. Hence, there exist at least $99-10\cdot 9>1$ vertices that are neighbor of all of them.
09.05.2020 13:00
Suppose that we have a vertex with degree $90$ , name it $A$ . $X_i$ be the set of all vertex with degree $i$ . If in middle of $A$'s neighbors we have at least $10$ member of one of the $X_i$ the problem is proved . So we have at most $9$ members of every $X_i$ , because we have $10$ sets and degree of $A$ is $90$ , so every $X_i$ have exactly $9$ members and now we have $9$ vertex with degree $90$ in middle of $A$'s neighbors so because we have $99$ vertex at all so we have $X_j$ such that $|X_j|<10$ so every member of $X_j$ are neighbor of all the member of $X_{90}$ and the problem is proved . So suppose that $|X_{90}|=0$ and at least one of the $X_{82}$ , … , $X_{89}$ isn't empty . Give $B$ one of the member of that set . $B$ has at least $82$ neighbors and we have at most $9$ set so we can find at least $10$ member of one of the $X_i$ and the problem is proved . The last situation is when all of the vertexes are of degree $81$ and the problem is obviously proved .
27.07.2021 01:19
Let $x_k$ be the number of nodes with degree $k$. Then, we double count the number of pairs $(A,B)$ where $\text{deg }B = k$. This, gives by comparing choosing $A$ first vs. choosing $B$ first, \[k\cdot a_k = \# \text{ of } (A,B) \leq 99\cdot 9\]Thus, $a_{81}\leq 11$, for $82\leq m \leq 89$, $a_m \leq 10$, and $a_{90}\leq 9$. Thus, \[99 = \sum_{k=1}^{90} a_k \leq 11+8\cdot 10 + 9 = 100\]Therefore, all $a_k$ bounds are strict, with one exception which is exactly one lower than the bound. Thus, there must be a node with degree 90, call it $P$. Additionally, note that \[\sum_{k=1}^{89} |a_k-9| = \sum_{k=1}^{89} (a_k-9) = (99-a_{90}) - 9\cdot 9 \geq 9\]Thus, since $P$ is connected to all but 8 nodes, there exists some $k$ such that $P$ has less than $|a_k-9|$ missed nodes to $a_k$, which is equivalent to $P$ having 10 edges going to $a_k$, and we have proved existence. $\blacksquare$.