2
$\begingroup$

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.

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

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?

$\endgroup$
  • $\begingroup$ E and F each have degree three? shouldn't it be 0? $\endgroup$ – Chin Apr 2 '13 at 21:43
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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