+1 vote
189 views
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.
| 189 views

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)C2. ===> 9C2 = 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 5C2 =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

0

nice explanation  Shaik Masthan