Library / IMO Team Selection Test /11 of 20

IMO Team Selection Test

Combinatorics Difficulty 8.4 Shortlist Prove it United States

Let $n$ be an even positive integer, and let $G$ be an $n$ -vertex graph with exactly $\frac{n^2}{4}$ edges, where there are no loops or multiple edges (each unordered pair of distinct vertices is joined by either 0 or 1 edge). An unordered pair of distinct vertices $\{x, y\}$ is said to be amicable if they have a common neighbor (there is a vertex $z$ such that $xz$ and $yz$ are both edges). Prove that $G$ has at least $2^{\binom{n/2}{2}}$ unordered pairs of vertices which are amicable.

Solution

The key idea is to rephrase amicable pairs in terms of more familiar concepts. Let $N^k(v)$ denote the $k$ th neighbor set of $v$ , and $S$ the set of vertices of nonzero degree. Note that $N^2(v)$ contains $v$ for all $v \in S$ , so a simple double-counting argument yields
$\begin{align*} 2(\text{number of unordered amicable pairs}) + |S| &= \sum_{v \in S} |N^2(v)| \\ &= \sum_{v \in S} \left| \bigcup_{u \in N(v)} N(u) \right| \\ &\ge \sum_{v \in S} \max_{u \in N(v)} |N(u)| \\ &\ge \sum_{v \in S} \frac{1}{|N(v)|} \sum_{u \in N(v)} |N(u)| \quad (\text{by averaging over all } u \in N(v)) \\ &= \sum_{\text{edges } uv \in E(G)} \left( \frac{|N(u)|}{|N(v)|} + \frac{|N(v)|}{|N(u)|} \right) \\ &\ge 2|E(G)|, \end{align*}$
where $E(G)$ denote the set of edges in $G$ , and we use AM-GM in the last step.
Thus the number of (unordered) amicable pairs is at least $|E(G)| - |S|/2 \ge n^2/4 - n/2 = 2^{\binom{n/2}{2}}$ , as desired.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.