recategorized by
9,686 views
26 votes
26 votes

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 
recategorized by

4 Answers

Best answer
33 votes
33 votes

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

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.

Answer:

Related questions

49 votes
49 votes
7 answers
1
Kathleen asked Sep 13, 2014
11,377 views
The eigen vector $(s)$ of the matrix $$\begin{bmatrix} 0 &0 &\alpha\\ 0 &0 &0\\ 0 &0 &0 \end{bmatrix},\alpha \neq 0$$ is (are)$(0,0,\alpha)$$(\alpha,0,0)$$(0,0,1)$$(0,\al...
27 votes
27 votes
2 answers
2
1 votes
1 votes
1 answer
3
Kathleen asked Sep 13, 2014
5,086 views
Simpson's rule for integration gives exact result when $f(x)$ is a polynomial of degree$1$$2$$3$$4$
5 votes
5 votes
1 answer
4
Kathleen asked Sep 13, 2014
1,603 views
The differential equation $\frac{d^2 y}{dx^2}+\frac{dy}{dx}+\sin y =0$ is:linearnon- linear ...