2023 Chinese IMO National Team Selection Test

Proof. We represent individuals as vertices, friendships as edges, and use a graph to depict the problem. The given graph contains a connected subgraph $G=(V,E)$ satisfying $|E|\le |V|\le n$. We denote the degree of vertex $v$ as $d(v)$ and the number of individuals with whom $v$ has shaken hands as $\beta (v)$. Assume the proposition is false, implying that for any vertex $v$, we have $$(\ast )\beta (v)\ge (m-1)\cdot d(v)+1.$$ Observation: For every vertex $v_0$ with degree 1 (connected to $v_1$), () implies $\beta (v_0)\ge (m-1)\cdot d(v_0)+1=m$. Thus, we have $d(v_1)\ge m+1$. Consider the graph $G^{\prime }=(V^{\prime },E^{\prime })$ obtained by removing all vertices of degree 1 in $G$ along with their incident edges. Note that the number of removed vertices is equal to the number of removed edges. Therefore, $G^{\prime }$ is necessarily connected and satisfies $|E^{\prime }|\le |V^{\prime }|$. Hence, $G^{\prime }$ is either a tree or has a unique cycle. We will consider three cases.

(0) $G^{\prime }$ has only one vertex $v_1$. From the previous observation, we know that $d(v_1)\ge m+1$. This implies that $G$ has only $m+2$ vertices, and all edges are the ones connecting $v_1$ to all other vertices. However, in this case, $\beta (v_1)=0\le (m-1)d(v_1)$, which contradicts our assumption.

(1) $G^{\prime }$ has a vertex $v_1$ with degree 1. Then, $v_1$ must be connected to a vertex $v_0$ with degree 1 in $G$. From the previous observation, we know that $d(v_1)\ge m+1$, which implies that $v_1$ is connected to $d(v_1)-1\ge m$ vertices of degree 1 in $G$. Let $v_1$ be connected to $v_2$ in $G^{\prime }$. In this case, the inequality $\beta (v_1)\ge (m-1)d(v_1)+1$ becomes $$d(v_2)-1\ge (m-1)d(v_1)+1\ge m^2,$$ which implies $d(v_2)\ge m^2+1$. Considering the inequality () for $v_2$, we have $$\beta (v_2)\ge (m-1)d(v_2)+1\ge (m-1)(m^2+1)+1.$$ Note that the friends of $v_2$ and the people $v_2$ has shaken hands with are pairwise distinct, except when $v_2$ lies on a cycle of length 3, in which case $v_2$ shakes hands with both of its friends. From this, we conclude that $G$ has at least $$1+d(v_2)+\beta (v_2)-2\ge 1+(m^2+1)+(m-1)(m^2+1)+1-2=m^3+m>m^3$$ vertices, which contradicts $n\le m^3$.

(2) All vertices in $G^{\prime }$ have degree at least 2. In this case, $G^{\prime }$ forms a cycle $v_1\sim v_2\sim \cdots \sim v_t\sim v_1$, where indices are taken modulo $t$. From the previous observation, each vertex $v_i$ is connected to exactly $d(v_i)-2$ (in $G$) vertices of degree 1. Thus, for $v_i$, (*) implies: $$(d(v_{i-1})-2)+(d(v_{i+1})-2)+2\ge \beta (v_i)\ge (m-1)\cdot d(v_i)+1\ge 2d(v_i)+1.$$ Summing up these inequalities for all $i$, we arrive at a contradiction.

Therefore, we conclude that there exists a vertex $v$ such that $\beta (v)\le (m-1)\cdot d(v)$. Hence, the proposition holds. $\square$