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.

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

How do I find all of the non-isomorphic connected graphs with the degree sequence 233345?

share|cite|improve this question

The vertex of degree $5$ must be joined by an edge to each of the others, and we can pick out any of the remaining $5$ vertices to be the vertex of degree $4$, connecting it the vertex of degree $5$ and $3$ of the remaining vertices, like this:

enter image description here

Now one of the four unlabelled vertices must have degree $2$, and the rest must have degree $3$. If you make the top vertex the vertex of degree $2$ by connecting it to one of the bottom three vertices, your remaining edge must join the other two of the three bottom vertices. Show that the three graphs that you can get in that way are isomorphic to one another.

The alternative is to connect the vertex at the top to two of the bottom three vertices; again you can show that the three graphs that you can get in this way are isomorphic.

To complete the solution, you have to decide whether these two graphs are isomorphic to each other or not. HINT: Focus on the vertices adjacent to the vertex of degree $2$.

share|cite|improve this answer

Notice the degree $5$ vertex is adjacent to every other vertex in the graph, so we can ignore it and just find all non-isomorphic (possibly disconnected) graphs with degree sequence $1,2,2,2,3$. As N.S. notes in the comments, we must allow for disconnected graphs, because adding the final vertex of degree $5$ at the end will result in a connected graph, even if the subgraph with degree sequence $1,2,2,2,3$ is disconnected.

Start with the leaf vertex. Either it is adjacent to a degree $3$ vertex or a degree $2$ vertex. There is only one graph for the former case and one graph for the latter up to isomorphism (the first and second graph in the picture, respectively).

enter image description here

To finish, link a sixth vertex to every other vertex in the graph (this is the degree $5$ vertex we ignored at the beginning).

share|cite|improve this answer
So there are two non-isomorphic graphs that fit the degree sequence? – Anthony Dec 5 '12 at 4:36
@Anthony There are at least the two I've demonstrated. You'll want to explain to your audience why these are the only two. Try drawing out the two cases I mentioned (whether the leaf is adjacent to a degree $3$ vertex or a degree $2$ vertex) and see why there is only one possible graph for each case. Let me know if I can elaborate. – Austin Mohr Dec 5 '12 at 4:38
@AustinMohr Why do you get a connected graph after removing the degree 5 vertex? Note that if if you have a disconected one, adding the degree 5 vertex connects it ;) – N. S. Dec 5 '12 at 4:40
Yes please elaborate I'm afraid I'm lost. – Anthony Dec 5 '12 at 4:45
@Anthony Well if the remaining graph is disconnected, one componet would only have 1 or 2 vertices, and then what would the degrees be there ;) – N. S. Dec 5 '12 at 4:46

By the Handshaking Lemma, there are $\tfrac12(2+3+3+3+4+5)=10$ edges in these graphs. We can exhaustively enumerate the $6$-vertex $10$-edge graphs with vertex degrees between $2$ and $6$ using geng which comes with nauty:

geng 6 10:10 -d2 -D5

The 12 graphs generated can be viewed using showg and we can exclude the ones that do not have the desired degree sequence. The two that remain are:

The two graphs with the desired degree sequence

where the vertices are ascribed their degrees.

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.