Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
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

2 Answers 2

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|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|improve this answer

Your Answer

 
discard

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.