Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)$

share|cite|improve this question

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.