Arranging $m$ edges on a graph of order $n$.

Question

I am new to graph theory and combinatorics, and thought of a question yesterday that I couldn't find the answer to.

Is there a formula for counting the number of ways to arrange $m$ edges on a graph of order $n$?

Answer 1

There are $\binom{n}{2}$ possible ways to place the edges, so there are $2^{\binom{n}{2}}$ possible arrangements of edges on a graph with $n$ vertices. You have $m$ such edges, so you simply want to consider subsets of size $m$. Thus, $\binom{ \binom{n}{2} } { m}$ gives you the count.