# Finding all graphs with a certain vertex degree sequence

I've been given the following problem as homework:

Q: How many graphs are there (up to isomorphism) with score (3, 3, 3, 3, 3, 3, 6)? Also, do this for (3, 3, 3, 3, 3, 3).

The "score" is the ordered list of degrees for the vertices in a graph; that is, the vertex degree sequence. For example, if a graph has score (3, 3, 3, 3, 3, 3), this means it has 6 vertices, each with degree 3.

I'm honestly pretty lost as to how to start here. "Up to isomorphism" means ignoring isomorphisms of the same graph (I'm guessing).

My attempts so far: I realize that for the first score, one of the points (with degree 6) is connected to all others, and they're all arranged in some way.

What approach do I take to finding all graphs with some score up to isomorphism?

Note: Please do NOT give me the solution to the question since this is homework. Just looking for tips and strategies.

-
What is the score of a graph? –  Qiaochu Yuan Apr 25 '12 at 0:43
Just edited that into the question. –  Casey Patton Apr 25 '12 at 0:45

Draw pictures. It will help. Don't be afraid to consider different cases, unless there are really just too many cases.

For the $(3,3,3,3,3,3,6)$ one, let the vertex with degree $6$ be $A$, and the other vertices be $B$ through $G$. Now you know that $A$ is connected to $B$, so $B$ must be connected to two other vertices in order to have degree $3$. Suppose without loss of generality that $B$ is also adjacent to $C$ and $D$. Now what might $C$ by adjacent too? How many more edges does it need? Where does that lead?

For the $(3,3,3,3,3,3)$ problem, call the vertices $A$ through $F$. WLOG $A$ is connected to $B$, $C$, and $D$. Now $E$ and $F$ each have degree three. What happens if $E$ and $F$ are not connected to each other? What happens if they are?

-
E and F each have degree three? shouldn't it be 0? –  Chin Apr 2 '13 at 21:43