The Gateway to Computer Science Excellence
+16 votes

Consider a simple connected graph $G$ with $n$ vertices and $n$ edges $(n > 2)$. Then, which of the following statements are true?

  1. $G$ has no cycles
  2. The graph obtained by removing any edge from $G$ is not connected
  3. $G$ has at least one cycle
  4. The graph obtained by removing any two edges from $G$ is not connected
  5. None of the above 
in Graph Theory by Veteran (52.2k points)
reshown by | 1.8k views

I think 'c' won't be ans because there will be exactly one cycle (as the graph is connected) not atleast. So only option 'd' is correct.

2 Answers

+21 votes
Best answer

This seems like multiple answer questions.

Here we have $n$ vertices & $n$ edges. So we must have cycle.

So (C) has at least one cycle is True & (A) is false.

(D) The graph obtained by removing any two edges from $G$ is not connected $\rightarrow$ This is true, for graph of $n$ vertices to be connected, we need at least $n-1$ edges. If we remove $2$ out of $n$, we get $n-2$ edges, which can connect at max $n-1$ vertices. $1$ Vertex at least will be disconnected. So D is true.

(B) is false as if graph is cyclic graph then removing any edge will not disconnect graph.

Answer $\rightarrow$ (C) & (D).

by Boss (41.9k points)
edited by

Consider case of a Cycle , each cycle(Cn) is going to have n vertices and n edges

now if u delete any 2  edges of cycle the graph will always be disconnected this proves (d) is  answer

(C) is the answer bcz max number of egdes required to connect n nodes in tree is n-1 hence adding 1 more edge leads to atleast one cyle

hence c and d

Thanks :)

how a cycle will be connected if we remove 2 adjacent edges?
I got it ... i did it by thinking vertices sryy :( i will edit that

Option (C) might not be correct because they have used the word "at least one cycle" while a graph with n vertices and n edges, graph will contain exactly 1 cycle.

But 'at least' contains the possibility of 'exactly one', hence option (C) also can be considered as true statement.

Option (c) can be thought as

Average vertex degree will be $\frac{2e}{n} = \frac{2(n)}{n} = 2$

Yes, if we remove 2 edges, graph will be disconnected.

completely agree with @ Manu thakur here "Attest " won't be right it had "exactly one" then it would have been also the option so only "d" right here

What if the graph is a tree then there will be no cycle so then how will atleast one cycle condition be satisfied?

please comment on this:

I think I have asked the same question do have the answer to my doubt?
No i think only option d will be correct.
Even I think the same but nobody has validated the answer.
How can one form a connected graph of $n$ vertices and $n$ edges without forming a cycle? These are the basic things given in any Graph Theory text.
ohh yes.. missed the point it should be equal number of edges as well and so tree cannot form as in tree always #edges=#vertices-1
Ah thank you sir missed the equal number of edges and vertices part.Thanks Alot.Doubt cleared.
+3 votes
if there are n vertices if you want to make it as a connected graph , there should be at least n-1 edges. hence if we remove two edges, it wont be a connected graph hence answer :d
by Boss (11k points)
(c) is also true rt?

No, C is not true as the graph will have exactly 1 cycle.

But exactly one cycle doesn't mean at least one cycle is not true rt?
'exactly one' is a subset of 'atleast one'. Both are not equivalent.
Yes. Both are not equivalent. But for exactly one, even at least one is true, not the other way.
@arjun sir

how c is correct ?

'exactly one' (1) is a subset of 'atleast one' (0,1) . Both are not equivalent.
^Yes, but whenever exactly one is TRUE, at least one is also true. i.e.,

exactly one $\implies$ at least one


at least one need not imply exactly one.
got !! thanx sir

for given question i have doubt on option c, bcoz range of at least 1 = [1,.....infinity)


now {2,3,4,...infinity} subset of [1,2,...infinity) so it hav no of cycle is only possible is one , to being a statement true if it fails for any counterexample then it should not be true there are so many counterexamples for that at least one is false so c should not be the answer
Answer is D.
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
50,741 questions
57,251 answers
104,652 users