Graph Theory

Question

Answer 1

For S1---

|v|=8, |E|=13,  There is theorem

CSPG with no K3 -------->e<=(2n-4), e is the no. of edges, n is no. of vertices and CSPG is connected simple planner graph

contrapositive of theorem is e>(2n-4)--------->CSPG with K3

so as in the question 13>(2*8-4) so this graph have K3, so here min 3 color required

So S1 is true

 

For S2---

r=(e-n+k+1)--------1 where e is the no. of edges, n is no. of vertices, k is no. of component in graph

as in the statement mentioned it is planner and have even degree 0 and 2 possible but not 4, 6, 8…. in that case it will be not planner because K5 will present

2+2+2+2…..n times = 2*e

e=n put in equation 1

r=n-n+k+1 = k+1, so all k component’s inner version can be colored with 1 color and one outer region required 1 color so it is 2 colorable

if we have few verices with 0 degree then it is isolated verex which can be colored with 1 color.

so this statement also true

Ans is c