1
$\begingroup$

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

3 Answers 3

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

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

  • 0
    I know it's kind of against the rules but is there any way you could just give me the answer this is the last problem that I'm having trouble with and I'm just not getting it I don't know if there is any hope of me actually understanding it at this late hour.2012-12-05
2

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

1

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.