The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
114 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.
in Graph Theory by Active (1.2k points) | 114 views

1 Answer

+4 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)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

by Veteran (61.8k points)
0

nice explanation  Shaik Masthan

Related questions

+3 votes
0 answers
5
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,807 questions
54,713 answers
189,259 comments
79,694 users