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
    So there are two non-isomorphic graphs that fit the degree sequence?2012-12-05
  • 0
    @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.2012-12-05
  • 0
    @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 ;)2012-12-05
  • 0
    Yes please elaborate I'm afraid I'm lost.2012-12-05
  • 0
    @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 ;)2012-12-05
  • 0
    But I need connected graphs not disconnected I'm not following2012-12-05
  • 0
    Ok I understand the reason why the disconnected graph is necessary now, how would I go about actually justifying this though and saying that these are the only two possibilities, why wouldn't the graph suggested in the answer below also be an answer?2012-12-05
  • 0
    @Anthony The graph in that answer still needs some edges before it is complete. Once the edges are added in two nonisomorphic ways, the resulting graphs will agree with the two I describe.2012-12-05
  • 0
    I'm not quite sure that I understand, how could I add a vertex and have it connect to all of the other vertices without it being isomorphic to any other graph I made where I just added a vertex?2012-12-05
  • 0
    Please join me in chat: http://chat.stackexchange.com/rooms/6622/chat-for-austin-and-anthony2012-12-05
  • 0
    It's is saying I need 20 reputation points to use the chat and I unfortunately do not have that.2012-12-05
  • 0
    @Anthony I'm sorry this has been a frustrating experience for you. All I can say in this limited space is I suggest you try drawing the two cases I described. Try to put together an argument with statements like "I cannot connect these two vertices" and "I must connect these two vertices" based on the requirements of the degree sequence.2012-12-05
  • 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.