Multiple choice

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?

  1. For every subset of k vertices, the induced subgraph has at most 2k-2 edges

  2. The minimum cut in G has at least two edges

  3. There are two edge-disjoint paths between every pair of vertices

  4. There are two vertex-disjoint paths between every pair of vertices
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

Keep practicing — related questions