Question

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

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

Answer 1

The correct option is D There are at least 2 vertex-disjoint paths between every pair of vertices

Given graph G contains n vertices and 2n - 2 = 2(n-1) edges.

So spanning tree must contains 2n - 4 edges. If G can be partioned into two edge disjoint spanning tree.

Then for any tree

$2e={\sum }_{i=1}^n{d}_i$

belongs to a tree if each $d_i$ is positive and e = n - 1

But in given problem e = 2n - 4 = 2(n-2)

So there are at least two vertex-disjoint paths between every pair of vertices.