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

option d

for this question i will recommend to to draw a full binary tree having 3 levels... now duplicate all the edges for example (from root we have one edge to left subtree and another to right subtree so just try adding another edge from root to left and another edge from root to  right subtree and so on) then try eliminating options .. you will find you cant  convinve yourself enough to eliminate option a so just leave it ... but when you will check option d you will be sure that this is false so tick that

Answer 2

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

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.

All these repetitive 2's don't give you a hint?

Since two edge-disjoint (or distinct) Spanning Trees can be carved out of G, Options B and C can immediately be said True.

 

Now, total edges = (2n-2).

Edges in 1 Spanning tree = (n-1) //fact.

Edges in both the spanning trees combined = (2n-2).

This means, the graph has 2 Spanning Trees, and that's it. No other egde.

If the whole graph of n vertices has (2n-2) edges, then intuitively it seems that a subgraph of k vertices will have (2k-2) edges.

 

I'll use proof by contradiction now.

Let the subgraph have k vertices. The remaining portion of the graph has (n-k) vertices.

Let's say the subgraph has (2k-1) edges // I assigned 1 extra edge in the subgraph.

So, the remaining portion has (2n-2) - (2k-1) edges.

=> 2n - 2k - 1

=> 2(n-k) - 1 edges.

Since this remaining portion of (n-k) vertices has 2(n-k) - 1 edges,
this means that it CAN NOT have two edge-disjoint spanning trees.
Because we'll have one more than maximum edges required for Spanning Trees,
which, as defined by the question, shouldn't be the case.

 

So, Option A is True, as well.

 

Which makes Option D our answer.