G is a graph on n vertices and 2n - 2 edges. The edges of G can be partitioned…
GATE · 2008 · CS
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 of 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 157 students.
Sign up free to check your answer
Sign up freeLoading lesson…