# Find all the non-isomorphic graphs whose degree sequence is $(6,3,3,3,3,3,3)$

Sorry I'm new here, can someone please help me out with this question. I missed a couple of lectures and I don't even know where to start. I'm trying to find all the non-isomorphic graphs whose degree sequence is $(6,3,3,3,3,3,3)$

-
Welcome to math.SE. A few tips: It's considered good form to put the question in the post, even if it's also in the title. Also, this looks like a homework question. If it is, please use the homework tag. People will still be happy to provide answers (or better yet, useful hints). –  Brett Frankel Mar 27 '12 at 23:49

Hint: Imagine a central vertex with degree 6 connected to the other six vertices (say, arranged on a circle). To get the vertices on the circle to have degree 3, each one must be connected to two others on the circle. If we label the vertices on the circle $v_1$ to $v_6$, then, without loss of generality, $v_1 \sim v_2$ and $v_2 \sim v_3$. After that, you have some freedom in adding edges.

Try it! See how many nonisomorphic ways you can find to fill in the missing edges.

-

I’m going to assume that you’re intended to consider only simple graphs, i.e., graphs with no loops and no multiple edges.

The key is the vertex of degree $6$: there are only six other vertices, so it must be connected to each of the others. That gives you a sort of asterisk, or six-pointed star:

                                   *   *
\ /
*----*----*
/ \
*   *


Each of the other vertices needs two more edges, and clearly none of those edges can go to the central vertex: it’s done. Clearly you could connect the outer vertices in a ring to make a sort of six-spoked wheel; can you find any other way to give each a degree of $3$?

If you’re allowed loops or multiple edges, the problem becomes significantly more complicated.

-