in Graph Theory
1,428 views
1 vote
1 vote

The possible number of faces of simple graph G with degree sequence 3, 3, 3, 3, 3, 3, 6 ______

  1.   5,6
  2.   6,7
in Graph Theory
1.4k views

1 Answer

1 vote
1 vote
Best answer

As there are 7 entries in degree sequence so ,

No of vertices = 7

Now applying Handshaking Theorem , we have

        Sum of degrees    =    2 * No of edges

==>  2 e   =  3 * 6  + 6

==>  e      =  24 / 2   =  12

Now assuming the planarity and assuming only one connected component and hence applying Euler's formula we have :

No of faces   =   e - n + 2

                    =   12 - 7 + 2

                    =    7  

In general ,

No of faces of a planar graph with k connected components = e - n + k + 1

So minimum possible number of faces for a planar graph will be 7 as found by having no of connected components  =  1

So number of possible number of faces will be 6 with the given number of edges and vertices only if it is non planar..

With this assumption,

2) should be the correct answer..

selected by

4 Comments

Didn't understood handshaking theorem.

What will be number of edges for $5,4,3,2,2,2$ ?
0
0
Also v - e + r = 2 holds for connected and planar graphs. What can be said when above formulae doesn't hold? How this can be used to talk about planarity and connectedness
0
0
for (5,4,3,2,2,2)

number of edges will be 9 as:

2e = sum of degrees of all the vertices

2e = 5+4+3+2+2+2

e= 9
1
1

Related questions