GATE CS 1995 Q1.25 — Graphs: Connectivity, Matching, Colouring

To find the minimum number of edges in a connected cyclic graph on $n$ vertices, we can analyze the properties of connected graphs:

1. Connected Acyclic Graph (Tree): A connected graph with $n$ vertices that contains no cycles (a tree) has exactly $n - 1$ edges. This is the absolute minimum number of edges required to keep $n$ vertices connected.
2. Introducing a Cycle: Adding any edge between two non-adjacent vertices in a tree creates exactly one cycle. Therefore, to make the connected graph cyclic, we must have at least: $$\text{Minimum edges} = (n - 1) + 1 = n$$

For example, a cycle graph $C_n$ on $n$ vertices has exactly $n$ edges and is both connected and cyclic.

Thus, the minimum number of edges is $n$.