The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+11 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 
asked in Graph Theory by Veteran (59.6k points)
reshown by | 1.3k 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

+17 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).

answered by Boss (43k 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?
+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
answered by Boss (11.5k 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

Related questions

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

42,687 questions
48,653 answers
63,963 users