GATE CS 1993 Q8.1 — Graphs: Connectivity, Matching, Colouring

Let $G = (V, E)$ be a simple connected graph with $|V| = n$ vertices and $|E| = n$ edges, where $n > 2$.

We analyze each option based on fundamental properties of connected graphs:

1. Statement A and C (Existence of Cycles):
   • A minimally connected graph (a tree) on $n$ vertices has exactly $n - 1$ edges and contains no cycles.
   • Since $G$ is connected and has $n$ edges (which is $(n-1) + 1$), it must contain at least one cycle (specifically, it is a unicyclic graph containing exactly one cycle).
   • Therefore, Statement C is true and Statement A is false.
2. Statement B (Removing one edge):
   • If we remove an edge that lies on the cycle of $G$, the remaining graph still has $n$ vertices and $n-1$ edges, and it remains connected (it becomes a spanning tree).
   • Thus, removing any edge does not necessarily disconnect the graph. Therefore, Statement B is false.
3. Statement D (Removing two edges):
   • Any connected graph with $n$ vertices must have at least $n - 1$ edges.
   • If we remove any two edges from $G$, the resulting graph will have $n$ vertices and $n - 2$ edges.
   • Since $n - 2 < n - 1$, it is mathematically impossible for a graph with $n$ vertices and $n - 2$ edges to be connected.
   • Therefore, removing any two edges will always result in a disconnected graph. Thus, Statement D is true.

Hence, the correct statements are C and D.