0
$\begingroup$

How many simple graph with $n$ vertices (labeled) and every vertex of it has at least $2$ edges?

I have established some views of simple graph with $4$ vertices, but somehow I found a trouble to apply combinatorics method, counting how many graph satisfies the condition. Could you give me some help?

$\endgroup$
  • $\begingroup$ Counting graphs is often hard. $n=3$ is $1$ here because you need the whole triangle. For $n=4$ you can start with $K_4$. You can delete no edges, one edge in four ways or two edges in four ways, giving nine graphs. I wouldn't try to count five by hand. $\endgroup$ – Ross Millikan Mar 9 '18 at 16:18
  • $\begingroup$ there is oeis.org/A013922 which is the number of labelled graphs with 0 cutpoints. Not quite what you want though... (eg two triangles connected by an edge would not be in the list) $\endgroup$ – gilleain Mar 9 '18 at 16:41
  • 1
    $\begingroup$ You're trying to count 2-cores on $n$ vertices. Here's some reference: math.uwaterloo.ca/~nwormald/papers/coresnumber.pdf $\endgroup$ – Daugmented Mar 9 '18 at 17:06

Your Answer

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

Browse other questions tagged or ask your own question.