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.
GATE 2008 · Discrete Mathematics · Graph Connectivity · medium
Answer: D. There are at least 2 vertex-disjoint paths between every pair of vertices.
Verify option A (induced subgraph bound): Any spanning tree restricted to k vertices forms a forest with at most k-1 edges. Two trees together give at most 2(k-1) = 2k-2 edges in the induced subgraph. So A is TRUE.
Verify option B (minimum cut >= 2): Any cut separates G into two parts. Each spanning tree must have at least one edge crossing the cut. Since the two trees are edge-disjoint, at least 2 edges cross any cut. So min-cut >= 2 and B is TRUE.
Verify option C (2 edge-disjoint paths): Since min edge-cut >= 2, by Menger's theorem there exist at least 2 edge-disjoint paths between every pair of vertices. C is TRUE.
Check option D (vertex-disjoint paths): Edge-connectivity >= 2 does NOT imply vertex-connectivity >= 2. A graph with a cut vertex (vertex-connectivity = 1) can still have edge-connectivity 2. Counterexample: two triangles sharing a single vertex — each cut has >=2 edges but the shared vertex is a cut vertex. D is NOT necessarily true.