Track / Stage 5 / 297 of 400 #897 of 2000

Problem 897

AIME late

Combinatorics Difficulty 5.7 Prove it

3. Given that $n$ is a positive even number, graph $G$ has $n$ vertices and $\frac{n^{2}}{4}$

edges, and there are no loops or multiple edges (any two vertices are either connected by an edge or not connected). An unordered pair of distinct vertices $(x, y)$ is called "friendly" if they are adjacent to the same vertex (there exists a vertex $z$ such that $x z$ and $y z$ are both edges). Prove: Graph $G$ contains at least $2 \mathrm{C}_{\frac{n}{2}}^{2}$ friendly unordered pairs.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

3. Let $N^{k}(v)$ denote the set of points at a distance $k$ from point $v$ , and let $S$ denote the set of points with non-zero degree. Let the number of friendly unordered point pairs be $m$ .

Considering that for all $v \in S, N^{2}(v)$ contains point $v$ . Thus, by counting twice we get
$\begin{array}{l} 2 m+|S|=\sum_{v \in S}\left|N^{2}(v)\right| \\ =\sum_{v \in S}\left|\sum_{u \in N(v)} N(u)\right| \\ \geqslant \sum_{v \in S u \in N(v)}|N(u)| \\ \geqslant \sum_{v \in S} \frac{1}{|N(v)|} \sum_{u \in N(v)}|N(u)| \end{array}$
(average over all $u \in N(v)$ )
$=\sum_{u v \in E(G)}\left(\frac{|N(u)|}{|N(v)|}+\frac{|N(v)|}{|N(u)|}\right) \geqslant 2 E(G) \text {, }$

where $E(G)$ is the set of edges in $G$ , and the last step uses the AM-GM inequality.
Thus, $m \geqslant E(G)-\frac{|S|}{2} \geqslant \frac{n^{2}}{4}-\frac{n}{2}=2 \mathrm{C}_{\frac{\pi}{2}}^{2}$ .

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.