Question

(a) Suppose that a connected planar graph has six vertices, each of degree three. Into how many regions is the plane divided by a planar embedding of this graph? 1. (b) Suppose that a connected bipartite planar simple graph has e edges and v vertices. Show that є 20-4 if v > 3.

Answer 1

a) For a connected planar graph Vertices = 6 Degree of each vertices = 3 So, we know by Euler's formula n(G) + f(G) = e(G) + 2 where n(G) = number of vertices f(G) = number of faces e(G) = number of edges and G denotes the graph so n(G) = 6 find e(G), first measure the sum of degrees. S.O.D = 6 times 3 = 18 So, 2e(G) = sum of degree = 18 e(G) = 9 The number of regions divided will be equal to number of faces So, substituting values in Euler formula 6 + f(G) = 9 + 2 f(G) = 5 \r\n e rightarrow edges f rightarrow faces v rightarrow vertices A bipartite is a graph with no cycles of odd number of edges. Hence if the edges were to be even, then in bipartite graph every face must have atleast 4 sides. So 4f would count every edge 2 times.