# Counting labelled graphs with k edges and n vertices

Is there a way to count labelled graphs (simple graphs - without loops and without multiple edges) with k edges and n using combinatorics methods without having to draw them?

For example - How many labelled graphs are there with 3 edges over the vertices {a, b, c, d, e, f}.

Please just provide me with a way (if there's any) and I would post an answer to the example question

• There are $\tbinom{n}{2}$ possible edges, out of which you choose $k$, so this gives a total of $\tbinom{\tbinom{n}{2}}{k}$ graphs. – Parzan Jan 30 '18 at 22:35
• Are the edges labeled as well? – Mauve Jan 31 '18 at 5:09

HINT: An edge is between two vertices. And assuming the graph is simple, we cannot choose the same vertex pair twice. Then first of all, how many unordered vertex pairs are there when we have $6$ vertices? (Unordered means $\{a,b\} = \{b,a\}$ for all $a,b$) Secondly, how many ways are there of choosing three distinct vertex pairs among them? Note that since it's labelled graph, we don't have to consider isomorphism.