Consider a simple connected graph G with n vertices and n+1 edges (n > 2). Then, which of the following statements are true? A. G has no cycles B. The graph obtained by removing any edge from G is not connected C. G has at least one cycle D. The graph obtained by removing any two edges from G is not connected E. None of the above

GATE 1993 · Discrete Mathematics · Graph Connectivity · easy

Answer: C and D are true. G has at least one cycle (cycle rank 2) and there exist two edges whose removal disconnects it.

1. Compute cycle rank of G: Cycle rank = (n+1)-n+1 = 2. G has 2 independent cycles. A (no cycles) is FALSE; C (at least one cycle) is TRUE.
2. Evaluate statements B and D: B: removing any single cycle edge does not disconnect G (the rest of that cycle provides an alternate path). B is FALSE. D: since cycle rank = 2, there exist two edges (one per independent cycle) whose simultaneous removal eliminates all alternate paths and disconnects G. D is TRUE.