 Solution

ID: past-exam-of-the-probability-statistics-and-options-i-course-of-the-university-of-oxford/2009/r/1/vi/solution

Q_{2}

and the drawn cube

Q_{3}

are planar. For

k \geq 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 \geq 3

vertices has at most

2 n - 4

edges, whereas

Q_{k}

has

n = 2^{k}

and

m = k 2^{k - 1} \geq 2 n

. Thus

Q_{k} is planar exactly for k = 2, 3 in the requested range k \geq 2.

 New to topics? Read the docs here!