Maths Olympiad Prep

Library / /1 of 3

Combinatorics Difficulty 4.7 AIME Prove it Romania

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

Solution

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

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

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.