GATE 2008
March 14, 2025GATE 2008
March 14, 2025GATE 2008
| Question 42 |
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?
| For every subset of k vertices, the induced subgraph has at most 2k–2 edges | |
| The minimum cut in G has at least two edges | |
| There are two edge-disjoint paths between every pair to vertices | |
| There are two vertex-disjoint paths between every pair of vertices |
Question 42 Explanation:
→ In Spanning tree n nodes require n-1 edges. The above question they mentioned 2 disjoint spanning trees. So, it requires n-1 + n-1 = 2n-2 edges. Except option D everything is correct.
> Option A: True: Subgraph with k vertices here is no chance to get more than 2k−2 edges. Subgraph with n−k vertices, definitely less than 2n−2k edges.
-> Option B: True: Take any subgraph SG with k vertices. The remaining subgraph will have n−k vertices. Between these two subgraphs there should be at least 2 edges because we are taken 2 spanning trees in SG.
-> Option C: True: A spanning tree covers all the vertices. So, 2 edge-disjoint spanning trees in G means, between every pair of vertices in G we have two edge-disjoint paths (length of paths may vary).
> Option A: True: Subgraph with k vertices here is no chance to get more than 2k−2 edges. Subgraph with n−k vertices, definitely less than 2n−2k edges.
-> Option B: True: Take any subgraph SG with k vertices. The remaining subgraph will have n−k vertices. Between these two subgraphs there should be at least 2 edges because we are taken 2 spanning trees in SG.
-> Option C: True: A spanning tree covers all the vertices. So, 2 edge-disjoint spanning trees in G means, between every pair of vertices in G we have two edge-disjoint paths (length of paths may vary).
Correct Answer: D
Question 42 Explanation:
→ In Spanning tree n nodes require n-1 edges. The above question they mentioned 2 disjoint spanning trees. So, it requires n-1 + n-1 = 2n-2 edges. Except option D everything is correct.
> Option A: True: Subgraph with k vertices here is no chance to get more than 2k−2 edges. Subgraph with n−k vertices, definitely less than 2n−2k edges.
-> Option B: True: Take any subgraph SG with k vertices. The remaining subgraph will have n−k vertices. Between these two subgraphs there should be at least 2 edges because we are taken 2 spanning trees in SG.
-> Option C: True: A spanning tree covers all the vertices. So, 2 edge-disjoint spanning trees in G means, between every pair of vertices in G we have two edge-disjoint paths (length of paths may vary).
> Option A: True: Subgraph with k vertices here is no chance to get more than 2k−2 edges. Subgraph with n−k vertices, definitely less than 2n−2k edges.
-> Option B: True: Take any subgraph SG with k vertices. The remaining subgraph will have n−k vertices. Between these two subgraphs there should be at least 2 edges because we are taken 2 spanning trees in SG.
-> Option C: True: A spanning tree covers all the vertices. So, 2 edge-disjoint spanning trees in G means, between every pair of vertices in G we have two edge-disjoint paths (length of paths may vary).