GATE CS 2004 Q79 — Graphs: Connectivity, Matching, Colouring

To find the number of simple graphs on $n$ labeled vertices with at least $\frac{n^2 - 3n}{2}$ edges, we can analyze the total possible edges and the number of "missing" edges.

Step 1: Find the maximum number of edges
The maximum number of edges in a simple graph with $n$ labeled vertices is given by: $$M = \binom{n}{2} = \frac{n(n-1)}{2} = \frac{n^2 - n}{2}$$

Step 2: Determine the condition on the number of edges
We want the number of edges, $e$, to satisfy: $$e \ge \frac{n^2 - 3n}{2}$$ Since $e$ cannot exceed the maximum possible edges $M$, the range of $e$ is: $$\frac{n^2 - 3n}{2} \le e \le \frac{n^2 - n}{2}$$

Step 3: Calculate the number of such graphs
The number of ways to choose $e$ edges out of $M$ possible edges is $\binom{M}{e}$. Summing this over the valid range of $e$ gives the total number of graphs: $$\text{Total Graphs} = \sum_{e = \frac{n^2 - 3n}{2}}^{\frac{n^2 - n}{2}} \binom{\frac{n^2 - n}{2}}{e}$$

Step 4: Simplify using binomial symmetry
Using the identity $\binom{N}{r} = \binom{N}{N-r}$, we can substitute $k = M - e$, which represents the number of missing edges. Let's find the limits for $k$:

• When $e = \frac{n^2 - n}{2}$ (maximum edges), the number of missing edges is: $$k = \frac{n^2 - n}{2} - \frac{n^2 - n}{2} = 0$$
• When $e = \frac{n^2 - 3n}{2}$ (minimum edges), the number of missing edges is: $$k = \frac{n^2 - n}{2} - \frac{n^2 - 3n}{2} = \frac{2n}{2} = n$$

Rewriting the summation in terms of $k$: $$\text{Total Graphs} = \sum_{k=0}^{n} \binom{\frac{n^2 - n}{2}}{k}$$

This matches Option D.