GATE CSE 2008 | Question: 42

Question

$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$?

• A. For every subset of $k$ vertices, the induced subgraph has at most $2k-2$ edges.
• B. The minimum cut in $G$ has at least $2$ edges.
• C. There are at least $2$ edge-disjoint paths between every pair of vertices.
• D. There are at least $2$ vertex-disjoint paths between every pair of vertices.

Comments

Any cyclic graph makes d false

---

I am not able to visualize this question.

---

Edge disjoint spanning trees are spanning trees that do not have any edges in common. 

Answer 1

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

Comments

@Arjun Sir:- I didn't get how you proved a and b to be true, can you pls explain in more simple terms

---

Lets take any subgraph of $G$ with $k$ vertices- let it be G1. The remaining subgraph will have $n-2$ vertices- let it be G2. Since a spanning tree covers all the vertices of a graph, there must be an edge connecting some vertex in G1 to some vertex in G2. Since, we have 2 spanning trees for G, there must be 2 such edges connecting G1 and G2. And this proves (b) is true.

---

The key point is spanning tree for a graph of n nodes will have n-1 edges as it is a tree and a tree has this property.

---

gt it for b but
"in the subgraph with k  vertices, we cannot have more than 2k-22k−2 edges as this would mean that in the other subgraph with n−k vertices, we would have less than 2n-2k2n−edges, making 2 spanning trees impossible in it. So, (a) is also TRUE."
pls explain this

---

We have two subgraphs G1 and G2. G1 has k vertices and G2 has n-k vertices.

Consider G2. Since we have 2 edge-disjoint spanning trees for G, each vertex in G2 must have two edges leaving it. These edges has only two possibilities- either go to some other vertex in G2 or go to a vertex in G1. In both the cases, it won't add to a an edge in G1. So, maximum edges in G1 = |E| - 2(n-k)
=2n-2 -2n+2k
=2k-2

---

thnku Gate CSE and Arjun Sir for such wonderful and patient explanations!!!

---

@Arjun Sir and Gate CSE here I found a case in which D is true.

---

You may be able to get it. But the thing is you can also get a graph where (D) is FALSE. That is it is not true for all $G$. Whereas (A), (B) and (C) are TRUE for any graph.

You have got a graph where (D) is false?

---

Srry for the late reply sir, and yes I got an example where it will be false

---

I'm adding Counter for option D as I thought it'll be useful. Take two copies of K4(complete graph on 4 vertices), G1 and G2. Let V(G1)={1,2,3,4} and V(G2)={5,6,7,8}. Construct a new graph G3 by using these two graphs G1 and G2 by merging at a vertex, say merge (4,5). The resultant graph is two edge connected, and of minimum degree 2 but there exist a cut vertex, the merged vertex.

Source :- http://geeksquiz.com/gate-gate-cs-2008-question-42/

---

can u please elaborate options C and D @ arjun sir

---

Sir I am not getting how in G2 we are getting no. Of edges 2*(n-k). Even if every vertex has atleast degree 2 we can't just say that no. Of edges will be 2 times no. Of vertices.

Please someone clear ny doubt. Thanx

---

If we have two graphs with G1 having $k$ vertices and G2 having $n-k$ vertices, then every vertex in G2 will have a degree of atleast 2 as G has two edge disjoint spanning trees.

So $2(n-k) = 2e$ gives $e=n-k$

Now G1 should have atmost $(2n-2) - (n-k)$ edges which is $(n+k) -2$. So how is option a) correct?

Where am I going wrong ? @Arjun

---

How G2 has 2(n-k) edges. Anyone please clarify.

---

How K4(2n-2)edge has at least minimum 2 edge cut ??

---

I am not able to understand Akash Kanse's example for option D:

I'm adding Counter for option D as I thought it'll be useful. Take two copies of K4(complete graph on 4 vertices), G1 and G2. Let V(G1)={1,2,3,4} and V(G2)={5,6,7,8}. Construct a new graph G3 by using these two graphs G1 and G2 by merging at a vertex, say merge (4,5). The resultant graph is two edge connected, and of minimum degree 2 but there exist a cut vertex, the merged vertex.

G3 should be 3 edge connected, as shown below, right?

---

Consider G2. Since we have 2 edge-disjoint spanning trees for G, each vertex in G2 must have two edges leaving it.

must have two or must have at least two edges??

---

Can any one explain edge disjoint path and vertex disjoint path meaning

---

good explanation

---

If n = 1, you have only one spanning tree (the root). This violates the condition of having two spanning trees given in question. The smallest graph which satisfies this question is the complete graph on 4 vertices

---

How to come up with counter examples in the exam?

---

U can't, u have to leave it and go 🫠

Answer 2

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

Comments

@rajesh pradan your 2nd graph is not spanning tree...u cant traverse all vertices in one go..

---

a spanning tree T of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G.

I think the definition  of spanning tree satisfy G2.

n=8V  (n-1 =7 edges  and no cycles which denotes a tree) and cover all Vertices. As well subgraph of G.

---

For option b if it says atleast three edges then it will be wrong as shown in picture if cut is taken as only vertex 10 and other contains remaning vertices then minimum cut has only 2 edges..

And this option says that every vertex has degree of atleast 2 and it is indeed true becaus There is two Spanning trees possible with disjoint edge set.  

Answer 3

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

Comments

@srestha

I think example given by you is wrong for n vertices there should be 2n-2 edges

In your example n=8 so there should be 14 edges , but in your example there are 12 edges

---

Your Graph is not as per the question.

No of edges are less.

---

@srestha the two graphs need to merged at a vertex, then only it will satisfy the condition given in the question, which is : n vertices and 2*n-2 edges

Answer 4

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

Comments

Yeah, for that you should have some spare vertices and edges.

---

yes

---

i dont think we will ever have some spare vertices bcoz  every vertex will be included in the first spanning tree only.