Past exam of the probability, statistics and options I course of the University of Oxford / 2009 / R / 1 / vi / Solution

The square $Q_2$ and the drawn cube $Q_3$ are planar. For $k\ge 4$, the subdivision in part (v) prevents planarity by Kuratowski's theorem. One can also check the edge count directly: a triangle-free simple planar graph with $n\ge 3$ vertices has at most $2n-4$ edges, whereas $Q_k$ has $n=2^k$ and $m=k{2}^{k-1}\ge 2n$. Thus