Thread: Proof of n-cube

Write down a proof that the n-cube cannot be realized as a planar graph for any n >=4.

I know I want to use the inequality of kF<=2E
and F=E-V+2 but I am not sure how to find the values.
A 4 cube has 16 nodes, and k = 3, so there are 48 edges, and 16 vertices. So there is 34 faces for it to be planar. But 102 is not less than 96 so a 4 cube is not planar.

Not so sure how to make this into a proof though. Any help would be much appreciated.

Originally Posted by smellatron

Write down a proof that the n-cube cannot be realized as a planar graph for any n >=4.

I know I want to use the inequality of kF<=2E
and F=E-V+2 but I am not sure how to find the values.
A 4 cube has 16 nodes, and k = 3, so there are 48 edges, and 16 vertices. So there is 34 faces for it to be planar. But 102 is not less than 96 so a 4 cube is not planar.

Not so sure how to make this into a proof though. Any help would be much appreciated.

The 4-cube has 16 vertices and 32 edges (4 edges meet at each vertex, and each edge connects 2 vertices). If the graph is planar then Euler's formula v–e+f=2 tells you that there must be 18 faces. But each face of the cube has 4 edges, and each edge is shared between 2 faces, so 18 faces would need 36 edges—contradiction, so the graph is not planar.

If n>4 then the graph of the n-cube contains the graph of the 4-cube as a subgraph. So the n-cube's graph must also be non-planar.