Gate CS-2008 Question Paper With Solutions

Q. 6 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) For every subset of k vertices, the induced sub graph has a most 2k – 2
edges.

(B) The minimum cut in G has a least two edges

(C) There are two edges-disjoint paths between every pair of vertices

(D) There are two vertex-disjoint paths between every pair of vertices.

Answer: (D)

Explanation:

Gate CS-2008 Question Paper With Solutions

Learn More:   Gate ME-2018-2 Question Paper With Solutions

LEAVE A REPLY

Please enter your comment!
Please enter your name here