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'm new to graph theory and I don't plan to become a serious student of graph theory either. My book suggests that there are $11$ non-isomorphic graphs of order $4$, but I can't see why.

I know that the most naive approach is that I can use brute force and draw four vertices and then try to connect two vertices by an edge in such a way that I don't get isomorphic graphs in each step. But then the question is, how should I know I have counted all possibilities at the end? And when the size of the graph becomes larger, how should I know I'm not counting two isomorphic structures more than once?

To be more precise, I have 5 questions about determining the number of non-isomorphic graphs with $n$ vertices:

  1. Is there an algorithmic approach for creating all non-isomorphic graphs of a certain order $n$?
  2. Does it have anything to do with graphic sequences and Havel-Hakimi algorithm or something?
  3. Is it possible to count the number of non-isomorphic graphs with $n$ vertices without actually knowing them or it's still an open problem?
  4. Is it possible to partially solve this by using group theory?
  5. How can I see that there are $11$ non-isomorphic graphs with $4$ vertices without brute force?
share|improve this question

3 Answers 3

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.

A picture of the eleven possible (up to isomorphism) simple graphs on four vertices is easily sketched.

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). 4-Node Graphs with 0,1,5,6 Edges

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). 4-Node Graphs with 2,4 Edges

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. 4-Node Graphs with 3 Edges

share|improve this answer

If you are just after a count you can compute this using the Polya Enumeration Theorem. What you want here is the cycle index of the edge permutation group $G$ of the complete graph $K_4$, which is a tetrahedron (this observation helps visualize the cycle structure of the permutations). The permutations of $G$ can be enumerated as follows.

There is the identity, which contributes $$a_1^6.$$ We can fix one vertex and rotate the other three, which gives, when applied to the edges, $$4\times 2\times a_3^2.$$ We can rotate by 180 degrees about the midpoints of two opposite edges, fixing those edges, for $$3\times a_1^2 a_2^2.$$ We can reflect, mapping the midpoints of two opposite edges onto each other, followed by a 90 or 270 degree rotation, giving $$3\times 2\times a_2 a_4.$$ Finally we can do a single squish, exchanging the vertices of one edge, which gives $$6\times a_1^2 a_2^2.$$ This yields the cycle index $$Z(G) = \frac{1}{24} \left(a_1^6 + 8 a_3^2 + 3 a_1^2 a_2^2 + 6 a_2 a_4 + 6 a_1^2 a_2^2\right)$$ which is $$Z(G) = \frac{1}{24} \left(a_1^6 + 8 a_3^2 + 9 a_1^2 a_2^2 + 6 a_2 a_4\right).$$ It follows that the ordinary generating function of unlabelled graphs on four vertices by the number of edges is given by $$Z(G)(1+z) = 1/24\, \left( 1+z \right) ^{6}+3/8\, \left( 1+{z}^{2} \right) ^{2} \left( 1+z \right) ^{2}+1/3\, \left( 1+{z}^{3} \right) ^{2}\\+1/4\, \left( 1+{z}^{2} \right) \left( 1+{z}^{4} \right)$$ which expands to $$Z(G)(1+z) = 1+z+2\,{z}^{2}+3\,{z}^{3}+2\,{z}^{4}+{z}^{5}+{z}^{6}.$$ It follows that there are $$\left.Z(G)(1+z)\right|_{z=1} = 11$$ nonisomorphic graphs on four vertices.

The following link does this Polya Enumeration computation for graphs of an arbitrary number of vertices. Here is another interesting Polya Enumeration II.

share|improve this answer
    
The link posted by Bulberage is excellent reading and there are no barriers to understanding due to complex notation. I hope my solution can be useful in the sense that we make en effort to keep it simple. –  Marko Riedel Dec 10 '13 at 0:20

Your third and fourth questions are related. You can count the number of non-isomorphic graphs on $n$ vertices by looking at the orbits of labelings of the edges of $K_n$ with two colors, under the action of the automorphism group of the edges of $K_n$. This can be done with Polya enumeration, which builds on Burnside's lemma, and which you are likely already familiar with from group theory. You may find this helpful, as it demonstrates this process for counting the graphs on $4$ vertices.

share|improve this answer

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.