It is known that each two of the 12 competitors, that participated in the finals of the competition “Mathematical duels”, have a common friend among the other 10. Prove that there is one of them that has at least 5 friends among the group.
Problem
Source: V International Festival of Young Mathematicians Sozopol 2014, Theme for 10-12 grade
Tags: combinatorics, graph theory
17.10.2019 20:01
EDIT. Unfortunately, there is a flaw. $7\cdot 12=84$, not $96$ as written (the red text below). Very sorry, my bad (thanks @yunxiu!). Either I had multiplied in my mind $8\cdot 12$ instead of $7\cdot 12$ or I had forgotten the multiplication table. Hope it's not the latter one! Anyway, this argument can be used to prove there is a vertex with degree at least 4 (thou it could be done in an easier way), so I leave it as it was. Let $G$ be the given graph with $12$ vertices. For the sake of contradiction, assume its maximal degree is at most $4$. Let $\overline{G}$ be the complement of $G$. Furthermore we work only with $\overline{G}$. All degrees of that graph are at least $7$. For any $v\in V(\overline{G})$, by $N[v]$ we denote all neighbours of $v$ plus $v$ itself. Every two vertices $u,v$ of $\overline{G}$ cannot cover the rest of the vertices, i.e. $N[u]\cup N[v]\neq V(\overline{G})$. Indeed, otherwise it would contradict the given condition for $G$. It just means the domination number of $\overline{G}$ is at least $3$. Denote by $\Delta$ the max degree of $\overline{G}$, so $\Delta\geq 7$, and let $v$ be a vertex with degree $\Delta$. We have $$2|E(\overline{G})|= \sum_{u\in N[v]} d(u) + \sum_{u\in V\setminus N[v]} d(u)\,\,\,\,\,\,\,\,\,\, (1)$$The idea is to estimate the two summands in the RHS, compare to the LHS and get contradiction since $2E(\overline{G})\geq \color{red}7\cdot 12=96$ (because any vertes has degree at least $7$). The first summand in $(1)$ is at most $\Delta(\Delta +1)$. The number of terms(edges) counted in the second summand can be partition into two components. 1) number of counted cross-edges between $N[v]$ and $V\setminus N[v]$ 2) number of edges counted inside $V\setminus V[v]$. Note, that every $u\in V\setminus V[v]$ is not connected with some other vertex in $V\setminus V[v]$. Hence, the terms in 2) are at most ${(11-\Delta)(11-\Delta-2)}$. Any vertex in $N[v]$ is not connected with at least one other vertex in $V\setminus N[v]$. Thus, the terms of 1) are at most $(\Delta+1)(11-\Delta-1)$. So, the RHS is at most $$\Delta(\Delta+1)+ (11-\Delta)(9-\Delta)+ (\Delta+1)(10-\Delta)=\Delta^2-10\Delta+109$$Hence, we get $$96\leq \Delta^2-10\Delta+109\,\,\,\,\,\,\,\,\,\, (2)$$Putting in $(2)$, $\Delta=7,8$ we get contradiction, thus it remains $\Delta=9,10$. Remembering each vertex in $N[v]$ cannot be connected with all vertices in $V\setminus N[v]$ we easily get that one of vertices in $V\setminus N[v]$ has degree at most $5$, which again is contradiction. Comment. There is an interesting result of Vizing that connects the domination number $\gamma$ of a graph $G$ with $n$ vertices, and the number of edges of $G$. Namely $|E|\leq \frac{1}{2}(n-\gamma)(n-\gamma+2)$. Unfortunately, applying that theorem doesn't work here. No wonder, since the graphs for which that result is sharp have isolated vertices. In this problem the minimal degree is pretty large. Btw, I used the Vizing method in $(1)$ here.
20.09.2020 15:47
The official solution. Let us denote the competitors by $A_1,A_2,\dots,A_{12}$. For the sake of contradiction, assume every student has at most $4$ friends. First, we prove it's impossible someone to have less than $4$ friends. 1) Suppose $A_1$ has only one friend (let it be $A_2$), then $A_1$ and $A_2$ do not have a mutual friend, contradiction. 2) If $A_1$ has two friends (let these be $A_2$ and $A_3$), then the common friend of $A_1$ and $A_2$ can only be $A_3$ and therefore $A_2$ and $A_3$ are friends. Then each of $A_2$ and $A_3$ have at most two friends out of $A_4,\dots, A_{12}$. This means that someone among $A_4,\dots, A_{12}$ (let it be $A_4$) is not known by $A_2$ and $A_3$. Now $A_1$ and $A_4$ do not have a common friend, contradiction. 3) Suppose $A_1$ has three friends, let them be $A_2, A_3$ and $A_4$. If among $A_2, A_3$ and $A_4$ there are only two friends (let it be $A_2$ and $A_3$), then $A_1$ and $A_4$ do not have a common friend, contradiction. Therefore, there are at least two pairs of friends between $A_2, A_3$ and $A_4$. Each of $A_2, A_3$ and $A_4$ has at most 4 friends, a total of at most 12 friends. That means the friends of $A_2, A_3$ or $A_4$ among the other 8 competitors $A_5,\dots, A_{12}$ are at most $12 -3 -2\cdot 2 = 5$ (12 friends without the three friendships with $A_1$ and without the two pairs of friends between $A_2, A_3$ and $A_4$, each of which counted twice). Hence someone among $A_5,\dots,A_{12}$ (let it be $A_5$) is not a friend with any of $A_2, A_3$ and $A_4$ and then $A_1$ and $A_5$ do not have a common friend, contradiction. The argument above implies everyone has exactly $4$ friends. Lemma. Each competitor has exactly four friends, and among them there exist two non-intersecting pairs of friendship. Proof. It suffices to prove the lemma for $A_1$. Let the friends of $A_1$ be $A_2, A_3, A_4$ and $A_5$. Suppose there exist three pairs of friends between $A_2, A_3, A_4$ and $A_5$. Then the number of students among $A_6,\dots, A_{12}$ which are friends with at least one of $A_2, A_3, A_4,A_5$ are at most $4\cdot 4- 4 -3\cdot 2 = 6$. This means that there is a competitor (let it be $A_6$) among $A_6,A_7,\dots,A_{12}$ who is not friends with $A_2, A_3, A_4$ and $A_5$ and then $A_1$ and $A_6$ have no common friend, contradiction. Therefore there are at most two pairs of friends among $A_2, A_3, A_4, A_5$. Since each of $A_2, A_3, A_4,A_5$ has a friend among the rest tree of them, WLOG the pairs of friends are $A_2,A_3$ and $A_4,A_5$. $\blacksquare$ Further, each of $A_2, A_3, A_4,A_5$ has two friends among $A_6,\dots,A_{12}$ and each of $A_6,\dots,A_{12}$ must have a friend among $A_2, A_3, A_4,A_5$. Then, exactly one of $A_6,\dots,A_{12}$ (let it be $A_6$) has two friends among $A_2, A_3, A_4,A_5$. If $A_6$ is a friend with $A_2$ and $A_3$ (respectively with $A_4$ and $A_5$), we get a contradiction with the Lemma applied to $A_2$ (respectively to $A_4$). Thus, WLOG we can consider that the friendships among $A_2, A_3, A_4$ and $A_5$ are: $A_2$ is a friend with $A_6$ and $A_7$; $A_3$ is friends with $A_8$ and $A_9$; $A_4$ is friends with $A_9$ and $A_{10}$; $A_5$ is friends with $A_{11}$ and $A_{12}$. The common friend of $A_4$ and $A_6$, as well as that of $A_4$ and $A_7$ can only be $A_{10}$. Therefore, $A_{10}$ is friend with $A_6$ and $A_7$, which contradicts the Lemma applied to $A_6$.
25.09.2020 16:37
Some more comments on the problem. Note that it can be stated in the following equivalent form. Any graph with $12$ vertices and minimum degree at least $7$ has domination number at most $2$. Thou the solution is a bashy casework, it's interesting to see what happens in the general case. Suppose we have a graph with $n$ vertices and minimum degree $\delta$. What can be said about its domination number? Here is an interesting result of Alon and Spencer (The Probabilistic Method). For any graph $ G$ with $ n$ vertices and minimum degree $ \delta$, the domination number is at most $$ \displaystyle \frac{\ln(\delta+1)+1}{\delta+1}n.$$It's of little help in this particular case $n=12,\delta =7$, but the result is sharp as $n\to \infty$. I commented more extensively on this in my blog.