The possible number of faces of simple graph G with degree sequence 3, 3, 3, 3, 3, 3, 6 ______
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..
64.3k questions
77.9k answers
244k comments
80.0k users