Let be the hypercube graph.

- (the complete graph with two vertices),
- (the square), and
- is constructed taking two copies of and adding an edge that connects each vertex of the first copy with the corresponding vertex of the second copy.

Easy: Find (chromatic number) for every .

Harder: Find every such that is planar.

Advertisements

is bipartite for every , so its chromatic number is 2. (Prove that it is bipartite).

Now, for the planarity problem, first let’s observe that is triangle free for every (easy to show), so then if it is planar, we can use Euler’s formula: . Let’s assume , then for every face we have at least 4 edges, then we have that (because we are counting every edge twice. Then, joining this with Euler's formula we get that .

We can check by hand that , and are planar.

For with , if it was planar, we should have that . It is easy to calculate by induction the number of edges and vertices of for all and check that that doesn't happen.

LikeLike