THE Fourteenth IMAR MATHEMATICAL COMPETITION

For every vertex $v$ of $Q_n$, let $v^{\prime }$ be the antipodal (opposite) vertex, consider the unique path in $T$ from $v$ to $v^{\prime }$ 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^{\prime }...yx...y^{\prime }$, from $x^{\prime }$ to $y^{\prime }$ has length at least $2n-1$. Finally, since $xy$ is an edge in $Q_n$, so is $x^{\prime }{y}^{\prime }$; adjunction of the latter to the unique path in $T$ from $x^{\prime }$ to $y^{\prime }$ yields the required cycle.