G is a graph on n vertices and 2n - 2 edges. The edges of G can be partitioned…
2008
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.
There are two edge-disjoint paths between every pair to vertices
- B.
The minimum cut in G has at least two edges
- C.
For every subset of k vertices, the induced subgraph has at most 2k-2 edges
- D.
There are two vertex-disjoint paths between every pair of vertices
Attempted by 73 students.
Show answer & explanation
Correct answer: D
Answer: The statement 'There are two vertex-disjoint paths between every pair of vertices' is NOT necessarily true.
Explanation:
Two edge-disjoint spanning trees each have n−1 edges, so their union has 2n−2 edges by hypothesis.
The existence of two edge-disjoint spanning trees implies the graph is at least 2-edge-connected (no bridges). Hence there are two edge-disjoint paths between every pair of vertices (edge-version of Menger), so the statement about two edge-disjoint paths is true.
For any subset of k vertices, each spanning tree induces at most k−1 edges on that subset, so the induced subgraph has at most (k−1)+(k−1)=2k−2 edges; thus the induced-subgraph bound is true.
However, having two edge-disjoint spanning trees does not force the graph to be 2-vertex-connected. Two vertex-disjoint paths between every pair would require vertex-connectivity at least 2 (no articulation vertex), which is a stronger condition than edge-connectivity ≥2.
Sketch of why the vertex-disjoint version can fail: it is possible to arrange two edge-disjoint spanning trees so that both trees use a single common vertex to connect two parts of the graph. Removing that vertex disconnects the union, so the union has an articulation vertex even though it has two edge-disjoint spanning trees. Therefore 'two vertex-disjoint paths between every pair' need not hold.