The GATE Grind

GATE 2008 CS – Question 42

Engineering Mathematics · Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) · 2 marks · Multiple choice

Graph G has n vertices and2n−2 edges partitionable into two edge-disjoint spanning trees. Which is NOT true?

  1. Every induced k-vertex subgraph has at most2k−2 edges.
  2. Minimum cut has at least2 edges.
  3. Every vertex pair has two edge-disjoint paths.
  4. Every vertex pair has two vertex-disjoint paths.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) Every vertex pair has two vertex-disjoint paths.

Explanation

We are sorry we couldn't write detailed soluition for this, we are working on it!, please consider asking your own AI, its just 2-3 clicks with very minimum effort

More Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions

All Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions →