DSA-Test 3-Question 10

Question

For which of the following scenarios does there exist a simple graph G = (V, E) 
satisfying the specified conditions? 
(A) It has 3 components 20 vertices and 16 edges. 
(B) It has 10 vertices, 38 edges, and more than one component. 
(C) It has 7 vertices, 10 edges, and more than two components. 
(D) It is connected and has 10 edges 5 vertices and fewer than 6 cycles.

Answer 1

option A:- It has 3 components 20 vertices and 16 edges.

we know that, For k components with n nodes, there should atleast n-k edges.

===> 20-3=17 edges should present, but we have 16 edges ===> This is False

check this for proof https://gateoverflow.in/237427/graph-theory

 

option B:- It has 10 vertices, 38 edges, and more than one component. 

Maximum edges we can get ( with 2 components only due to given that more than one component ).

Keep 1 vertex as one component, remaining all vertices are one component, then maximum edges = complete graph of (n-1) nodes ===> maximum edges = ^(n-1)C₂. ===> ⁹C₂ = 36,

but given that we have 38 edges, therefore given graph is not simple graph.

 

Option C :- It has 7 vertices, 10 edges, and more than two components. 

given that more than 2 components, therefore let check from 3

{1},{1},{5} components ===> Maximum ⁵C₂ =10 edges with {5} component ===> we can have simple graph.

 

Option D:- It is connected and has 10 edges 5 vertices and fewer than 6 cycles.

It is a complete graph of 5 vertices, Check the cycles

it should be more than 6 ===> Statement is False

Comments

nice explanation  Shaik Masthan