# GATE1993-8.1

2.3k 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
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.

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

edited by
1

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

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.
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.
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.
0
@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.
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
(c) is also true rt?
0

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

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

## Related questions

1
2.7k views
$\displaystyle \sum_{1\leq k\leq n} O(n)$, where $O(n)$ stands for order $n$ is: $O(n)$ $O(n^2)$ $O(n^3)$ $O(3n^2)$ $O(1.5n^2)$
Let $A$ and $B$ be sets with cardinalities $m$ and $n$ respectively. The number of one-one mappings from $A$ to $B$, when $m < n$, is $m^n$ $^nP_m$ $^mC_n$ $^nC_m$ $^mP_n$
The less-than relation, $<,$ on reals is a partial ordering since it is asymmetric and reflexive a partial ordering since it is antisymmetric and reflexive not a partial ordering because it is not asymmetric and not reflexive not a partial ordering because it is not antisymmetric and reflexive none of the above
Let A be a finite set of size n. The number of elements in the power set of $A\times A$ is: $2^{2^n}$ $2^{n^2}$ $(2^n)^2$ $(2^2)^n$ None of the above