Library / Fourteenth IMAR MATHEMATICAL COMPETITION /1 of 3

Fourteenth IMAR MATHEMATICAL COMPETITION

Combinatorics Difficulty 4.7 AIME Prove it Romania

Fix an integer $n \ge 2$ , let $Q_n$ be the graph consisting of all vertices and all edges of an $n$ -cube, and let $T$ be a spanning tree in $Q_n$ . Show that $Q_n$ has an edge whose adjunction to $T$ produces a simple cycle of length at least $2n$ .

Solution

For every vertex $v$ of $Q_n$ , let $v'$ be the antipodal (opposite) vertex, consider the unique path in $T$ from $v$ to $v'$ and orient its first edge away from $v$ . Since $T$ has fewer edges than vertices, some edge, say $xy$ , has been assigned two orientations. The (combinatorial) distance between two antipodes of $Q_n$ is $n$ in $Q_n$ , so it is at least $n$ in $T$ , and the unique path in $T$ , $x'...yx...y'$ , from $x'$ to $y'$ has length at least $2n-1$ . Finally, since $xy$ is an edge in $Q_n$ , so is $x'y'$ ; adjunction of the latter to the unique path in $T$ from $x'$ to $y'$ yields the required cycle.

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.