# Find all non-isomorphic symmetric graphs given the nodes degree

I have 5 nodes with the degree 2, 2, 2, 3, 5. How do I find all non-isomorphic graphs I can make out of these 5 nodes? All the nodes must be connected with eachother.

One way I think would work would be to bruteforce it by writing a chart for every possibility.

Like if A represents 2, B - 3 and C - 5 and where an X represents an edge.

  A A A B C
A   X X
A X     X
A X       X
B   X   X
C     X   2X


But that seems like it would be hard to not miss/add a graph and takes some time to do. Does any one know a way to do this?

• Loops are allowed
• Multiple edges between same two nodes are allowed
-
I assume from your example that you’re allowed to use loops; are you also allowed multiple edges? – Brian M. Scott Jul 29 '11 at 19:20
Wouldn't it be a bit odd to allow loops without also allowing multiple edges? (But of course you'd still have a math question there.) – Michael Hardy Jul 29 '11 at 19:32
I updated the question – user13901 Jul 29 '11 at 19:39
Your example doesn't seem to work out -- if I understand your X's correctly, then $B$ has $2$ edges instead of $3$ and $C$ has $3$ instead of $5$? – joriki Jul 29 '11 at 21:17
I think you mean isomorphic rather than isometric. Isometric refers to preserving distances. – Joseph Malkevitch Jul 29 '11 at 22:57

The valence 2 nodes can be thought of as adding an internal vertex to an existing edge. So we begin by looking at the number of graphs that have two vertices of valence 3 and 5. There are two of these. The first graph is a theta graph with an extra loop at one end. The second is a loop connected to two loops by an edge. Now we need to study the number of distinct ways to add 3 bivalent vertices to each graph.

For the first graph type there are two ways to add all three to the same edge, 3 ways to add them to different edges, and 2 ways to add them to 3 different edges. So that's 7 of the first type.

For the second graph type there are three ways to add them to the same edge, 7 ways to add them to two edges and 3 ways to add them to three edges. So that's 13 of the second kind of graph. So I get 20 total.

In summary, by looking at the graph with bivalent vertices removed, the analysis is simplified a bit, although it is still brute force.

-
Your first sentence is false since in the statement of the problem he allows loops. – AnonymousCoward Jul 29 '11 at 21:46
AH, wait, I am wrong since the graph must be connected. My apologies. – AnonymousCoward Jul 29 '11 at 21:48
@GottfriedLeibniz: I don't see what you mean. The graph is connected. – Grumpy Parsnip Jul 29 '11 at 21:48
@Jim, it's not connected if there's a degree 2 vertex with a loop. That's why Gottfried's first comment is mistaken, as Gottfried notes in the second comment. There is no objection to your answer. – Gerry Myerson Jul 29 '11 at 23:00
This way of solution will only work good on smaller graphs like this one. But I can't seem to find a better way of doing it. Thank you! – user13901 Jul 30 '11 at 10:47