1
$\begingroup$

How many graphs with vertex degrees (1, 1, 1, 1, 2, 4, 5, 6, 6) are there? Assuming that all vertices and edges are labelled. I know there's a long way to do it by drawing all of them and count. Is there a quicker, combinatoric way?

  • 0
    nauty is used for graph canonical labeling. It comes with a package "geng" which can generate graphs upto isomorphism under certain conditions, but degree sequence is not one of them.2013-04-16

1 Answers 1

5

There are none. By the hand shaking lemma we know that the number of degrees of odd degree must be even.

There are 5 vertices with odd degrees in your graph, these are the ones with degrees:

1,1,1,1,5