Question 18
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.