edited by
23,307 views
76 votes
76 votes

$G$ is a graph on $n$ vertices and $2n-2$ edges. The edges of $G$ can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for $G$?

  1. For every subset of $k$ vertices, the induced subgraph has at most $2k-2$ edges.
  2. The minimum cut in $G$ has at least $2$ edges.
  3. There are at least $2$ edge-disjoint paths between every pair of vertices.
  4. There are at least $2$ vertex-disjoint paths between every pair of vertices.
edited by

6 Answers

Best answer
63 votes
63 votes

There are $2$ spanning trees (a spanning tree connects all $n$ vertices) for $G$ which are edge disjoint. A spanning tree for $n$ nodes require $n-1$ edges and so 2 edge-disjoint spanning trees requires $2n-2$ edges. As $G$ has only $2n-2$ edges, it is clear that it doesn't have any edge outside that of the two spanning trees. Now lets see the cases:

Lets take any subgraph of $G$ with $k$ vertices. The remaining subgraph will have $n-k$ vertices. Between these two subgraphs (provided both has at least one vertex) there should be at least $2$ edges, as we have $2$ spanning trees in $G$. So, (B) is TRUE. Also, in the subgraph with $k$ vertices, we cannot have more than $2k-2$ edges as this would mean that in the other subgraph with $n-k$ vertices, we would have less than $2n-2k$ edges, making $2$ spanning trees impossible in it. So, (A) is also TRUE.

A spanning tree covers all the vertices. So, $2$ edge-disjoint spanning trees in $G$ means, between every pair of vertices in $G$ we have two edge-disjoint paths (length of paths may vary).  So, (C) is also TRUE.

So, that leaves option (D) as answer. It is not quite hard to give a counter example for (D).

edited by
26 votes
26 votes

Plz see below graph

Here it satisfies all constraints 2n-2 edges. 2 edge-disjoint spanning trees.

Imp:->> (in addition to some graphs shown like above )All wheel graphs with odd no. of nodes satisfy above 2  given constraint of question.

And now elimnate options.

(I think for option B if they will tell minimum cut edge is atleast 3 then also it is true..plz verify But atleast 2 includes atleast 3)

All options are true except D due to presence of cut vertex.

Note:- Edge-disjoint path :- pair of nodes can be connected by 2 diffrent paths which dont have any shared edges.

Vertex-disjoint path;--pair of nodes can be connected by 2 diffrent paths which dont have any shared vertices(nodes).

edited by
18 votes
18 votes

(A) satisfies here. Induced subgraph is a connected graph which is subgraph of main graph

(B) This is possible. It is a complete graph,So, if we remove only 1 edge the graph is not disconnected.Min cut must be atleast 2 edges.

(C) yes for every vertices there are two edge disjoint path

So, (D) is the ans. If u eliminate any two vertex , no edge will be disconnected.(conter example given by @Akash)

edited by
15 votes
15 votes

(A)For the case k=n, the induced sub-graph is the graph itself and it has $2n-2$ edges.

(B)Given from the description of the graph,G it has two edge-disjoint spanning trees.

Now there is a theorem which says, The cut-set of a connected graph G must contain at least one edge from every spanning tree of Graph G.

This graph has two edge-disjoint spanning trees and hence, this graph's cut-set would have minimum size of 2.(one-edge from each of the spanning tree). Note that, here we don't mean that the cut-set size is 2, but it means atleast 2.

So, this is true.

(C)Since there are two edge-disjoint spanning trees of G, there are indeed 2 edge-disjoint paths between every pair of vertices.

This is true.

Answer-(D)

Answer:

Related questions

39 votes
39 votes
7 answers
1
Kathleen asked Sep 11, 2014
56,655 views
Which of the following statements is true for every planar graph on $n$ vertices?The graph is connectedThe graph is EulerianThe graph has a vertex-cover of size at most $...