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?


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.