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

16 votes

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

- $G$ has no cycles
- The graph obtained by removing any edge from $G$ is not connected
- $G$ has at least one cycle
- The graph obtained by removing any two edges from $G$ is not connected
- None of the above

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

1

**hence c and d**

8

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.

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?

3

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.

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

0

@arjun sir

how c is correct ?

'exactly one' (1) is a subset of 'atleast one' (0,1) . Both are not equivalent.

how c is correct ?

'exactly one' (1) is a subset of 'atleast one' (0,1) . Both are not equivalent.

8

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

exactly one $\implies$ at least one

but

at least one need not imply exactly one.

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

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