70.2K

Verified Solution

Link Copied!

Abstain from plagiarizing others' responses and produce your own original answer.

9. (10 pts) While Euler's 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 Euler's theorem: - A simple, connected planar graph with n3 vertices and e edges must satisfy e3n6 - A simple, connected planar graph with n3 vertices, e edges and no cycles of length 3 must satisfy e2n4 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 k2k1, 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

Answer & Explanation Solved by verified expert

See Answer