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

Dark Mode

7,853 views

25 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

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

yes Sir in this year’s GATE the same question came from TOC. I thought that if in option it is given as * “ Language(L2) is CFL”* so it is not clear that whether they are only focusing on

so unless it is mentioned in the question to select the **strongest** one , we have to select the superset’s of the answers as well right?

0

1

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

@Arjun sir aren’t these the same statements? unable to differentiate :(

exactly one ⟹ at least one

but

at least one need not imply exactly one.

0