How do I find all of the non-isomorphic connected graphs with the degree sequence 233345?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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).
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
The 12 graphs generated can be viewed using
where the vertices are ascribed their degrees.