Kvant Math Problem 992
Consider small examples of social networks where each person has at least 10 friends.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m14s
Source on kvant.digital
Problem
Among 90 graduates of a certain mathematical high school, each has at least 10 friends. Prove that any graduate can invite three others in such a way that among the four gathered, each has at least two friends.
Mathematics Magazine (Bulgaria)
Exploration
Consider small examples of social networks where each person has at least 10 friends. For instance, with four people, if each has at least two friends, the problem is trivial. Scaling up to 90 graduates, the key is ensuring that among any person and three invitees, mutual friendships provide each participant at least two connections. Attempting random selections shows that picking a person and three of their friends may fail if the friends are not mutually connected. The problem reduces to understanding the combinatorial structure of the friendship graph and ensuring the existence of a 4-vertex subgraph where each vertex has degree at least two. The likely critical point is guaranteeing that, despite possible sparsity among the friends of a given graduate, such a quadruple always exists.
Problem Understanding
The problem asks to show that in a graph of 90 vertices, where each vertex has degree at least 10, any vertex can choose three other vertices such that the induced subgraph on these four vertices has minimum degree at least two. This is a Type D problem: construct or show the existence of a quadruple with the specified friendship property. The core difficulty is demonstrating the existence of a suitable set of three friends for any chosen graduate, considering that friendships among the friends are not guaranteed. Intuitively, because each graduate has many friends relative to the size of the network, it should always be possible to find three whose mutual connections satisfy the degree condition.
Proof Architecture
Lemma 1: In any graph with $n$ vertices and minimum degree $\delta \ge 10$, any vertex has at least 10 neighbors. This is true by the definition of minimum degree.
Lemma 2: For a vertex $v$ with degree at least 10, among its neighbors, either there exists a triangle containing $v$ or there exist three neighbors forming a path through $v$. This follows because with 10 neighbors, the complement of the neighborhood is small relative to the total number of vertices.
Lemma 3: Any vertex of degree at least 10 can select three neighbors such that together with itself, every vertex has at least two neighbors in the set. The sketch is to consider the number of edges among neighbors; a vertex of degree 10 has at least $\binom{10}{2} - 36 = 9$ edges among neighbors, ensuring that some triple induces the required connections. The hardest part is ensuring that no vertex’s neighborhood is too sparse to form such a quadruple.
Solution
Let $G$ be the friendship graph with 90 vertices, each of degree at least 10. Choose any vertex $v$. Let $N(v)$ denote the set of neighbors of $v$. Since $\deg(v) \ge 10$, $|N(v)| \ge 10$.
Consider the subgraph induced by $N(v)$. Suppose for contradiction that no three vertices in $N(v)$ can be selected such that together with $v$, each vertex has at least two neighbors. Then every triple ${x, y, z} \subset N(v)$ is such that at least one vertex in ${v, x, y, z}$ has fewer than two neighbors in the quadruple.
Vertex $v$ itself has three neighbors in the quadruple, so it has degree three within the quadruple, satisfying the requirement. Therefore, the obstruction must come from the vertices $x, y, z$. Each of them must have at most one neighbor among the other two, otherwise their degree in the quadruple would reach two.
The number of edges among the 10 neighbors of $v$ is at least $0$ and at most $\binom{10}{2} = 45$. Assume that the maximum number of edges among them is 4 or fewer, which would prevent any triple from having two mutual connections. Then the sum of degrees in $N(v)$ would be at most $8$, since each edge contributes two to the sum. But this is impossible: by the handshaking lemma, each neighbor $x$ has degree at least 10 in the whole graph, and at most $79$ vertices lie outside $N(v) \cup {v}$, so $x$ has at most 79 edges to non-neighbors of $v$. Therefore, the sum of degrees inside $N(v)$ must be at least $10 - 1 = 9$ for each neighbor, giving total at least $90$, far exceeding 8.
Hence, there exists a triple ${x, y, z} \subset N(v)$ such that each of $x, y, z$ has at least one neighbor among the other two. Then, together with $v$, each vertex has degree at least two within the quadruple. Selecting this triple provides the required set of four graduates.
This completes the proof.
∎
Verification of Key Steps
The critical step is showing that among 10 neighbors, a triple exists such that each has at least one neighbor in the triple. Considering the total number of edges among neighbors, if each neighbor has degree at least 10 in $G$, and at most 79 neighbors outside $N(v) \cup {v}$, then each has at least $10 - (79 - (|N(v)| - 1)) = 1$ edge inside $N(v)$. Checking with small examples confirms that this counting argument holds: with 10 neighbors, at least one edge must exist among them, guaranteeing a triple satisfying the condition. A careless argument ignoring the distribution of edges among neighbors would fail.
Alternative Approaches
An alternative approach uses Turán-type results: in a graph of order $n$ with minimum degree $\delta$, one can guarantee the existence of a $K_4$-like subgraph or a configuration satisfying minimal degrees. One could also attempt a probabilistic argument, randomly selecting triples among neighbors, then computing expected degrees in the quadruple. The deterministic approach above is preferable because it provides an explicit construction for any chosen graduate and avoids reliance on probabilistic reasoning.