3
$\begingroup$

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
  • 0
    I assume from your example that you’re allowed to use loops; are you also allowed multiple edges?2011-07-29
  • 0
    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.)2011-07-29
  • 0
    I updated the question2011-07-29
  • 0
    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$?2011-07-29
  • 0
    I think you mean isomorphic rather than isometric. Isometric refers to preserving distances.2011-07-29
  • 0
    @Joseph: fixed. Wrote isomorphic in the title and metric in the text.2011-07-30
  • 0
    @joriki: Sorry about not making that one clear, B -> B is a loop that adds two to the degree.2011-07-30
  • 0
    @user13901: Ah, my mistake :-)2011-07-30

1 Answers 1

3

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.

  • 0
    Your first sentence is false since in the statement of the problem he allows loops.2011-07-29
  • 0
    AH, wait, I am wrong since the graph must be connected. My apologies.2011-07-29
  • 0
    @GottfriedLeibniz: I don't see what you mean. The graph is connected.2011-07-29
  • 0
    @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.2011-07-29
  • 0
    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!2011-07-30