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.

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.

share|improve this question
    
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
add comment

2 Answers

up vote 3 down vote accepted

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?

share|improve this answer
    
E and F each have degree three? shouldn't it be 0? –  Chin Apr 2 '13 at 21:43
add comment

For the first case, since you know the one vertex is connected to all other vertices, delete it and arrive at the degree sequence (2, 2, 2, 2, 2, 2). Find all such graphs up to isomorphism. Then, for each graph you found, add the one vertex back and you're done with that case.

share|improve this answer
add comment

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.