GATE CS 2001 Q2.15 — Graphs: Connectivity, Matching, Colouring

To find the number of undirected graphs that can be constructed from a given set of $n$ vertices, we consider the possible edges between these vertices:

1. Total possible edges: In an undirected graph with $n$ vertices, any pair of distinct vertices can form an edge. The number of ways to choose a pair of vertices from $n$ vertices is given by: $$\binom{n}{2} = \frac{n(n-1)}{2}$$ This represents the maximum number of possible edges in a simple undirected graph of size $n$.
2. Constructing a graph: For each of these $\frac{n(n-1)}{2}$ possible edges, we have exactly $2$ choices:
   • The edge is present in the graph.
   • The edge is absent from the graph.
3. Total number of graphs: Since the choice for each edge is independent, the total number of distinct undirected graphs is: $$2 \times 2 \times \dots \times 2 \quad \left(\frac{n(n-1)}{2} \text{ times}\right) = 2^{\frac{n(n-1)}{2}}$$

Therefore, the correct option is D.