How many graphs on n labeled vertices exist which have at least (n2 - 3n)/2…

Concept: For a fixed universe of M independent binary items (each either “present” or “absent”), the number of ways to choose exactly k of them to be present is C(M, k). By the symmetry identity C(M, k) = C(M, M−k), counting “at least (M−n) present” is the same as counting “at most n absent” — summing C(M, k) over a window near one end of k equals summing C(M, j) over the mirrored window near the other end.

Application:

1. On n labeled vertices, the total number of possible (undirected) edges is M = n(n−1)/2 — every unordered pair of vertices is a candidate edge, and each candidate is independently either present or absent in a given graph.

2. The threshold given is (n2 − 3n)/2. Rewriting it in terms of M: (n2 − 3n)/2 = n(n−1)/2 − n = M − n.

3. So “a graph with at least M − n edges” is exactly “a graph with at most n missing edges” (since edges present + edges missing = M always).

4. For a fixed number of missing edges k (0 ≤ k ≤ n), the graph is fully determined by choosing which k of the M candidate pairs are absent: there are C(M, k) such graphs.

5. Summing over every allowed value of k gives the total count: the number of graphs with at most n missing edges is the sum from k = 0 to n of C(M, k), i.e. the sum from k = 0 to n of C(n(n−1)/2, k).

Cross-check:

1. Writing the count directly in terms of present edges (instead of missing edges) gives the sum from k = M−n to M of C(M, k) — a run of exactly n+1 consecutive terms ending at k = M.

2. Substituting j = M−k turns this into the sum from j = 0 to n of C(M, M−j).

3. The symmetry identity C(M, M−j) = C(M, j) converts that into the sum from j = 0 to n of C(M, j) — the same n+1-term sum obtained in the application steps above, confirming both ways of counting agree.

Result: the number of such graphs is the sum from k = 0 to n of C(n(n−1)/2, k).