, 2023

*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
$$(*) \qquad \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' = (V', E')$ 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'$ is necessarily connected and satisfies $|E'| \le |V'|$. Hence, $G'$ is either a tree or has a unique cycle. We will consider three cases.

(0) $G'$ 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'$ 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'$. 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'$ have degree at least 2. In this case, $G'$ forms a cycle $v_1 \sim v_2 \sim \dots \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$