search
Log In
16 votes
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 
in Graph Theory
reshown by
2.3k 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

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


edited by
1

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

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

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

Related questions

26 votes
6 answers
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)$
asked Sep 30, 2014 in Algorithms Kathleen 2.7k views
15 votes
3 answers
2
1.3k views
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$
asked Sep 30, 2014 in Set Theory & Algebra Kathleen 1.3k views
13 votes
3 answers
3
2k views
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
asked Sep 30, 2014 in Set Theory & Algebra Kathleen 2k views
16 votes
2 answers
4
2k views
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
asked Sep 30, 2014 in Set Theory & Algebra Kathleen 2k views
...