Question

In problems 3 through 6, imagine putting a small cube inside a larger cube and let G be the graph whose vertex set consists of the 8 corners of the small cube and the 8 corners of the larger cube (16 vertices total) and whose edge set consists of the edges in each cube (12 per cube) and the edges joining corresponding vertices of the two cubes (8 more), for a total of 32 edges. de 6. Is G planar? If so, draw a planar representation. If not, prove so by con- tradiction using either the circle-chord method or a violation an appropriate inequality

read exercise and do question 6

Answer 1

Answer: G is not planar... The given graph has 16 vertices and 32 edges. Thus if the graph is plannar then by Euler's formula we must have or, 16 32+f-2 or,f 18 But we know that for any plannar graph we must have f × 18-27 < 32. This is satisfied. Also a planar graph must satisfy e s 2v -4 Now 2v 4 2(16)- 4 32-4 28 But e 32, so e s planar. 2v - 4 it is not satisfied. Thus the Graph G is not