nice explanation Shaik Masthan

The Gateway to Computer Science Excellence

+1 vote

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.

+5 votes

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_{2}. ===> ^{9}C_{2} = 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 ^{5}C_{2} =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

52,315 questions

60,426 answers

201,749 comments

95,226 users