graph theory
I have been asked to draw all the non-isomorphic connected simple graphs, each with a degree sequence (2,2,3,3,3,3,4,4) I understand a non isomorphic graph is a graph where the relabelling of the vertices wont give the same graph. But I am lost to where to even start, or the best way to go about it.
Help
URL=http://s906.photobucket.com/user/michael_lews23/media/nonisomorphic_zps280581a7.jpg.html
Sent it last night, but would these be classed as non isomorphic?
First off, let me say that you can find the answer to this question in Sage using the nauty generator. If you're going to be a serious graph theory student, Sage could be very helpful.
count = 0
for g in graphs.nauty_geng("20 180:180"):
count = count+1
print count
The answer is 4613. But, this isn't easy to see without a computer program.
At this point, perhaps it would be good to start by thinking in terms of of the number of connected graphs with at most 10 edges. Then, all the graphs you are looking for will be unions of these. You should be able to figure out these smaller cases. If any are too hard for you, these are more likely to be in some table somewhere, so you can look them up.
Connected graphs of order n and k edges is:
n = 1, k = 0: 1
n = 2, k = 1: 1
n = 3, k = 2: 1
n = 3, k = 3: 1
n = 4, k = 3: 2
n = 4, k = 4: 2
n = 4, k = 5: 1
n = 4, k = 6: 1
n = 5, k = 4: 3
n = 5, k = 5: 5
n = 5, k = 6: 5
n = 5, k = 7: 4
n = 5, k = 8: 2
n = 5, k = 9: 1
n = 5, k = 10: 1
.
.
.
n = 10, k = 9: 106
n = 10, k = 10: 657
n = 11, k = 10: 235
I used Sage for the last 3, I admit. But, I do know that the Atlas of Graphs contains all of these except for the last one, on P7.
The graph isomorphism problem is "a curiousity" according to the Wikipedia article, because it is one of very few problems which are NP but not known either to be in P or to be NP-complete. There are algorithmic approaches, but these are not closely related to group theory except in the general sense of using symmetries, and they are often very tractable by known methods. Brendon McKay's NAUTY was the first to produce all the 11 vertex ($n=11$) graphs up to isomorphism, and can check most pairs of graphs up to 100 vertices for isomorphism rather readily.
OEIS A000088 gives a tablulation of known results for $n=0,1,2,\ldots,19$ and some useful references.
Pictures of the eleven possible (up to isomorphism) simple graphs on four vertices are easily sketched as you'll see below.
To prove these are exhaustive, one might focus on some graph properties that are preserved by isomorphism (graph invariants). An easy one is the number of connected components. As shown in the diagrams, we need to account for one graph with four components, one with three components, three with two components, and six that are connected (one component).
Other easy graph invariants are the number of edges, the collected degrees of vertices (degree sequences), and the number of 3- and 4-cycles (possibly zero).
Since the diagrams shown at the link above are arranged by number of edges, which ranges from $0$ (no edges) to $6$ (complete graph $K_4$), it's perhaps the way to begin, first to assure us that all eleven graphs really are non-isomorphic, and second to assure us there is no overlooked possibility.
The extremes (no edges, one edge, six edges) all give unique graphs, and a moments reflection will tell you that five edges also gives a unique graph (because you are picking any one of the edges of the complete graph to remove, and all those choices are equivalent).
There are two cases with two edges, which you should convince yourself differ by whether the edges connect or not, and that these exhaust all possibilities for two edges on four vertices.
The two cases with four edges are similarly distinguished by whether we remove two edges (from the complete graph) that connect or not. Note that removing two edges that do not connect leaves a four-cycle (each vertex has degree two), where removing two edges that do connect leaves one "terminal" vertex of degree one, so that these are clearly non-isomorphic (and exhaust all possibilities).
The three cases with three edges are the most interesting, because as a class these are closed under complementation. One (threeB) is the smallest nontrivial self-dual simple graph, a graph isomorphic to its complement. The other two (threeA and threeC) are complementary to each other and clearly not self-dual (threeC is connected and its complement is not; threeA contains a cycle and its complement does not).
To see that these exhaust the possibilities for three edges, note that any tree (a cycle-free connected graph) on four vertices will have precisely three edges. If a graph on four vertices with three edges has a cycle, that must be a triangle (3-cycle) since we don't have enough edges for anything bigger. Otherwise we have a tree, and the tree must either consist of one vertex of degree three connecting to the other three vertices, or else a path of three edges that connects all the vertices.
Best Answer
One way you can approach this problem is noting that the vertices with degree 2 can be "reduced" to an edge without changing degrees. So we want to find all non-isomorphic connected simple graphs with degrees (3,3,3,3,4,4) first. Consider the complement of this graph; you get (1,1,2,2,2,2) as the degrees. There are only a few ways in which this can happen: you can have a lone edge and a 4-cycle, a 3-path and a 3-cycle, or a 6-path. (I believe these are the only cases)
Next, convert these back into graphs and the question is reduced to finding edges (which could be the same edge, giving a 3-long "edge") to "lengthen" by inserting a vertex in the middle.