# Non-isomorphic connected graphs question

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

-

## 3 Answers

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:

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

-

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

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

-
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:

where the vertices are ascribed their degrees.

-