GATE CSE 1993 | Question: 8.1

Question

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

• A. $G$ has no cycles
• B. The graph obtained by removing any edge from $G$ is not connected
• C. $G$ has at least one cycle
• D. The graph obtained by removing any two edges from $G$ is not connected
• E. None of the above 

Comments

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.

---

Does at least one not imply exactly one also?

---

thanks

Answer 1

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

Comments

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.

---

@krishn.jh

Your figure is incorrect as a tree cannot have n vertices and n edges. For n vertices and n edges ,we have to consider a Cycle Graph only.

---

There should be exactly one cycle, right?

---

Btw in MSQ we should select all the possible answers also ! don’t just go for the strongest one.

That’s  why C is also correct!

---

In quality exams like GATE there is nothing called “strongest” unless it is mentioned in question. If a regular language is given and if CFL is an option, that is correct. Similarly if “exactly” is correct, “at least” is also correct as exactly implies “at least”. Even “not more than 1” is correct as “exactly one” does imply “not more than one”.

---

Arjun

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 CFL and neglecting that the language is regular as well OR they are saying that the given language is both regular and CFL. thats why i didn’t marked that option .

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? 

---

That’s always the case. You are a man but also a human being and and also a living being. Only due to solving bad questions students have these confusions.

---

Thanks sir! got it now🙌

Answer 2

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

Comments

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

---

No. A implies B is entirely different from B implies A. That's a Mathematical logic topic.

---

Arjun

okay sir ! thankyou!!

Answer 3

Given graph G has n vertices and n edges.We know that if G is acyclic then it must have n-1 edges(tree) so g has a cycle in it

 

The graph obtained by removing the edge may or may not result in a dis-connected graph.So option B is False.

 

Since we have n edges so it has  exactly 1 cycle …But does it imply atleast 1 cycle?

 

According to proposition logic exactly 1 → atleast 1 so option c is true but the converse (atleast 1 → exactly 1 )is false

 

The graph obtained by removing any two edges from G is disconnected.Consider a cycle graph if we remove two adjacent edges then the vertex common to the edges will get disconnected and if we remove non adjacemt edges it will make the graph disconnected as well.Since n-1 vertices are needed to minimally connect any graph so with n edges and removing 2 we will have n-2 edges in all graphs so its will always result in disconnected graphs

 

Correct answers are option C and D.

Answer 4

1) Always false. A graph with no cycles (also known as a tree) has n nodes and n−1 edges. Add one more edge and you're going to make a cycle somewhere.

2) Not necessarily true. Easy counterexample: a graph with n nodes and n edges that forms a circle (i.e. a single cycle). Take out an edge anywhere and the graph is still connected.

3) Always true, see (1). If "G has no cycle" is always false, then it always has at least one cycle.

4) Always true. Think about it like this: if it's a connected graph with n vertices and n edges, and you remove one edge, then you have n−1 edges. If it's still connected, then it's a tree. (If it is not connected, then we're done.) Now you have a tree. Remove any edge from a tree, and your tree is split into two connected components.