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?

  • 2
    The sum of the degrees must be even for there to be *any*, because each edge adds $2$ to the sum of the degrees.2012-12-01
  • 0
    There is a software package [nauty, by Brendan McKay](http://cs.anu.edu.au/~bdm/nauty/) that can automate the solution of feasible versions of such problems. See in particular the tool *geng* of that package.2012-12-01
  • 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