# Hypercube graph

Let $Q_n$ be the hypercube graph.

• $Q_1 = K_2$ (the complete graph with two vertices),
• $Q_2 = C_4$ (the square), and
• $Q_n$ is constructed taking two copies of $Q_{n-1}$ and adding an edge that connects each vertex of the first copy with the corresponding vertex of the second copy.

Easy: Find $\chi(Q_n)$ (chromatic number) for every $n$.

Harder: Find every $n$ such that $Q_n$ is planar.

$Q_n$ is bipartite for every $n$, so its chromatic number is 2. (Prove that it is bipartite).
Now, for the planarity problem, first let’s observe that $Q_n$ is triangle free for every $n$ (easy to show), so then if it is planar, we can use Euler’s formula: $v - e + f = 2$. Let’s assume $e \geq 4$, then for every face we have at least 4 edges, then we have that $\frac{4f}{2} < e$ (because we are counting every edge twice. Then, joining this with Euler's formula we get that $v < \frac{e}{2} + 2$.
We can check by hand that $Q_1$, $Q_2$ and $Q_3$ are planar.
For $Q_n$ with $n \geq 4$, if it was planar, we should have that $v < \frac{e}{2} + 2$. It is easy to calculate by induction the number of edges and vertices of $Q_n$ for all $n$ and check that that doesn't happen.