discrete mathematicsgraph theorygraph-isomorphism
Task:
Find all pairwise non-isomorphic graphs with $n\leq 4$ vertices.
I think that for $n = 1$ there is 1 such graph, for $n = 2$ – two, for $n = 3$ – there are 4 of them (shown in the photo), for $n = 4$ – 11 (shown in the photo). Can I combine all these sets into one, and say that there are only 18 pairwise non-isomorphic graphs with $n\leq 4$ vertices? Or, in this case, there will be graphs isomorphic to each other?
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.
As mentioned in the comments, a set of graphs (G) is pairwise non-isomorphic if for any pair of graphs (g, h) in G, g is not isomorphic to h.
You have a couple of options (at least). Lets call the starting set of graphs the base set and adding an edge to a graph an augmentation:
The first of these options is the easiest for small base sets (equivalently, for graphs on small numbers of vertices). For example, take the square - you can add a new edge to each of the vertices to get a graph on 5 vertices ... but of course all of these augmentations will be pairwise isomorphic.
The difficulty with the second approach is that augmenting different base graphs can lead to the same output graph. For example see this pair of augmentations:
Of course, you can follow the same procedure as in the first approach of simply filtering out these duplicates, but this becomes computationally expensive for larger graphs. A far better approach is described by Brendan McKay of canonical path augmentation. This involves rejecting augmentations that would lead to non-canonical child graphs, but it's a little long for this answer and described better elsewhere.
Best Answer
Yes, what you have is correct and so the total number will be $18$. Two graphs $G_1,G_2$ are isomorphic if there is a bijection $\phi:V(G_1)\to V(G_2)$ such that $xy\in E(G_1)\Longleftrightarrow \phi(x)\phi(y)\in E(G_2)$. In particular, since $\phi$ is a bijection, if two graphs are isomorphic they must have the same number of vertices.