Given a random labelled simple graph with n edges, when is it more likely to get a graph with more edges than vertices?

Question

That is, for what number of vertices n does there exists more simple labelled graphs (with n vertices) with more edges than vertices than simple labelled graphs (with n vertices) with more vertices than edges?

Answer 1

Let $e = {n \choose 2}$ be the number of possible edges of a graph with $n$ vertices.

There are ${e \choose k}$ labeled graphs with $k$ edges.

So there are $L = \sum_{k = 0}^{n - 1} {e \choose k}$ graphs with less edges than vertices.

Similarly, there are $M = \sum_{k = n + 1}^e {e \choose k}$ graphs with more edges than vertices.

You want to know when $L < M$. Exhaustively, you could write

$$ {e \choose 0} + {e \choose 1} + \cdots + {e \choose {n - 1}} < {e \choose {n + 1}} + {e \choose {n + 2}} + \cdots + {e \choose e} $$

We have ${e \choose 0} = {e \choose e}, {e \choose 1} = {e \choose {e - 1}}$ and so on (in general, ${e \choose k} = {e \choose {e - k}}$). Remove all such terms that are equal on both sides, and you'll have that $L < M$ when $M$ has strictly more terms than $L$. That is, when

$$ (n - 1) - 0 + 1 < e - (n + 1) + 1 $$

(the number of terms on both sides). Solve that, you get

$$ 2n < e = {n \choose 2} $$

which holds precisely when $n > 5$, according to this site for the lazy.