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

Dark Mode

Akriti sood
asked
in Graph Theory
Nov 28, 2016

1,428 views
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..**

0