0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Parzan Jan 30 '18 at 22:35
  • $\begingroup$ Are the edges labeled as well? $\endgroup$ – Mauve Jan 31 '18 at 5:09
0
$\begingroup$

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.

$\endgroup$

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.