+14 votes
1.6k views

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

reshown | 1.6k views
0

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

by Boss (41.1k points)
edited by
0

hence c and d

### Thanks :)

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

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.

+1
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.
0

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

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

please comment on this: 0
I think I have asked the same question do have the answer to my doubt?
0
No i think only option d will be correct.
0
Even I think the same but nobody has validated the answer.
+2
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.
+1
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
0
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)
0
(c) is also true rt?
0

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

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

how c is correct ?

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

exactly one $\implies$ at least one

but

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

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
0
Answer is D.

+21 votes
3 answers
1
+12 votes
3 answers
2
+11 votes
3 answers
3
+13 votes
2 answers
4
+15 votes
4 answers
5
+21 votes
3 answers
6
+27 votes
2 answers
7