While Eulers theorem gives a characterization of planar graphs in terms of numbers of vertices, edges and faces, it is hard to establish whether a graph is planar or not if it is difficult to count faces. There are a couple of other properties of simple, connected planar graphs that derive from Eulers theorem:

A simple, connected planar graph with n 3 vertices and e edges must satisfy e 3n 6

A simple, connected planar graph with n 3 vertices, e edges and no cycles of length 3 must satisfy e 2n 4

A popular architecture for parallel computers is a hypercube. A hypercube of dimension k, denoted by Qk, has 2k nodes, and each node is connected to k other nodes. The nodes can be embedded into a k-dimensional boolean vector, and nodes are connected to other nodes that differ along one of its coordinates. Thus, Q2 has nodes (0, 0),(0, 1),(1, 0),(1, 1), and has 4 edges. The node (0,0) is connected to (0,1) and (1,0). Q3 has nodes (0, 0, 0),(0, 0, 1),(0, 1, 0),(0, 1, 1),(1, 0, 0),(1, 0, 0),(1, 1, 0),(1, 1, 1). Node (1,1,1) is connected to nodes (0,1,1), (1,0,1) and (1,1,0). Note that the number of edges in a hypercube of dimension k is k 2 k1 , since each node has k edges, and we divide by 2 so as not to count the number of arcs twice. Other important facts about hypercubes is that every hypercube is a bipartite graph.

(a) Using the above facts, verify that Q3 is a planar graph.

(b) Using the above facts, show that Q4 cannot be a planar graph