USA IMO TST

Combinatorics Difficulty 8.3 Shortlist Prove it United States

For a finite simple graph $G$ , we define $G'$ to be the graph on the same vertex set as $G$ , where for any two vertices $u \neq v$ , the pair $\{u, v\}$ is an edge of $G'$ if and only if $u$ and $v$ have a common neighbor in $G$ . Prove that if $G$ is a finite simple graph which is isomorphic to $(G')'$ , then $G$ is also isomorphic to $G'$ .

We say a vertex of a graph is fatal if it has degree at least 3, and some two of its neighbors are not adjacent.

Solution

Claim — The graph $G'$ has at least as many triangles as $G$ , and has strictly more if $G$ has any fatal vertices.
Proof. Obviously any triangle in $G$ persists in $G'$ . Moreover, suppose $v$ is a fatal vertex of $G$ . Then the neighbors of $G$ will form a clique in $G'$ which was not there already, so there are more triangles. $\square$

Thus we only need to consider graphs $G$ with no fatal vertices. Looking at the connected components, the only possibilities are cliques (including single vertices), cycles, and paths. So in what follows we restrict our attention to graphs $G$ only consisting of such components.

Remark (Warning). Beware: assuming $G$ is connected loses generality. For example, it could be that $G = G_1 \sqcup G_2$ , where $G_1' \cong G_2$ and $G_2' \cong G_1$ .

First, note that the following are stable under the operation:
* an isolated vertex,
* a cycle of odd length, or
* a clique with at least three vertices.

In particular, $G \cong G''$ holds for such graphs.

On the other hand, cycles of even length or paths of nonzero length will break into more connected components. For this reason, a graph $G$ with any of these components will not satisfy $G \cong G''$ because $G'$ will have strictly more connected components than $G$ , and $G''$ will have at least as many as $G'$ .

Therefore $G \cong G''$ if and only if $G$ is a disjoint union of the three types of connected components named earlier. Since $G \cong G'$ holds for such graphs as well, the problem statement follows right away.

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.