Question

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

Answer 1

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..

Comments

Didn't understood handshaking theorem.

What will be number of edges for $5,4,3,2,2,2$ ?

---

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

---

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