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?
How many graphs with vertex degrees (1, 1, 1, 1, 2, 4, 5, 6, 6) are there?
1
$\begingroup$
combinatorics
graph-theory
-
0nauty 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
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