There are $24$ participants attended a meeting. Each two of them shook hands once or not. A total of $216$ handshakes occured in the meeting. For any two participants who have shaken hands, at most $10$ among the rest $22$ participants have shaken hands with exactly one of these two persons. Define a friend circle to be a group of $3$ participants in which each person has shaken hands with the other two. Find the minimum possible value of friend circles.
Problem
Source: 2018 China Southeast MO Grade 10 P7
Tags: combinatorics, graph theory
MarkBcc168
03.08.2018 13:14
Take the obvious graph interpretation. The answer is $\boxed{864}$, archived by a complete $4$-partite graph $K_{6,6,6,6}$.
Now we proceed to prove the bound. The claim is
Claim : Given any edge $uv$. The number of vertices $w$ which makes $u, v, w$ a $K_3$ is at least $\frac{\deg(u) + \deg(v) - 12}{2}$.
Proof : Clearly the number of edges incident to exactly one of $u, v$ is $\deg(u) + \deg(v) - 2$. At most $10$ edges is incident to a vertex which connects to exactly one of $u, v$. Thus at least $\deg(u)+\deg(v)-12$ must connect to a vertex adjacent to both $u,v$, implying the claim.
Sum up all these numbers over all ordered pair $(u,v)$ such that $uv\in E$. The number of $K_3$ is
\begin{align*}
\frac{1}{6}\sum_{uv\in E} \frac{\deg(u) + \deg(v) - 12}{2} &= \frac{1}{6}\left(\sum_{uv\in E} \deg(u) - \sum_{uv\in E} 6\right) \\
&= \frac{1}{6}\left(\sum_{u\in V} \deg(u)\sum_{v\in V, uv\in E} 1 - 12|E|\right) \\
&= \frac{1}{6}\left(\sum_{u\in V} \deg(u)^2 - 2592\right) \\
&\geqslant \frac{1}{6}\left[\frac{1}{|V|}\left(\sum_{u\in V}\deg(u)\right)^2 - 2592\right]\\
& = \frac{1}{6}\left(\frac{(2\cdot 216)^2}{24}-2592\right) \\
&= 864
\end{align*}as desired.
China_BW
10.07.2022 03:50