Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

Updates:

  • Loops are allowed
  • Multiple edges between same two nodes are allowed
share|improve this question
    
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
show 3 more comments

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.