[Math] Why there are $11$ non-isomorphic graphs of order $4$

Question

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?

Answer 1

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.