discrete mathematicsgraph theory
How many non-isomorphic simple graphs are there on n vertices when n is 2? 3?
4? and 5?
So I got…
$2$ when $n=2$
$4$ when $n=3$
$13$? (so far) when $n = 4$ But I have a feeling it will be closer to 16.
I was wondering if there is any sort of formula that would make finding the answer easier than just drawing them all out. And if not, if anyone could confirm my findings so far.
...in a directed graph, what makes it non isomorphic?
As an adjective for an individual graph, non-isomorphic doesn't make sense. You can't sensibly talk about a single graph being non-isomorphic. What we can talk about are sets of graphs which are pairwise non-isomorphic (i.e., any two graphs in the set are not isomorphic).
Intuitively speaking, two graphs $G$ and $G'$ are isomorphic if they have essentially the same structure (and non-isomorphic otherwise). Formally, two graphs are isomorphic if there's an edge-preserving bijection from the vertices of $G$ to the vertices of $G'$.
In the following example, the two red digraphs have essentially the same digraph: there is one node with two out-edges. An edge-preserving bijection (i.e., an isomorphism) in this case is $1 \mapsto 2$, $2 \mapsto 1$ and $3 \mapsto 3$.
There is no such bijection between the red and blue digraphs since they do not have the same in/out-degree sequences.
Is a set of vertices all isolated included? (some solutions say yes, but how can it then be called 'directed?')
The $n$-vertex null digraph (i.e. $n$ vertices and no edges) is consistently regarded as a directed graph.
How many nonisomorphic directed simple graphs are there with n vertices, when n is 2,3, or 4?
To answer this question requires some bookkeeping. The $2$-node digraphs are listed below. Note that I'm including the possibility of bidirectional edges (i.e., an edge from $A$ to $B$ and an edge from $B$ to $A$).
The number of digraphs grows quickly, and is given by Sloane's A000273. For $2$-, $3$- and $4$-node digraphs, the numbers are $3$, $16$, and $218$, respectively (allowing bidirectional edges).
If I was pressed to find these numbers, I'd get my computer to find them by:
This would be quite an inefficient generation method, but would be fast enough for $4$-node digraphs.
Can there be multiple graphs in the answer that have the same number of edges and the same in/ out degree totals, or does a distinct signature of edge # and in/ out degree total constitute a distinct graph?
There can be, here's an example:
and one without bidirectional edges:
In the table in the question there's a number of omissions (this is why I'd do it on a computer).
You've correctly observe e.g. that:
are not isomorphic, since the in/out-degrees don't match. For the same reason e.g.:
are also non-isomorphic. Similar omissions (where we flip edge directions) happen in other cases.
I also don't see a oriented 3-cycles with an isolated vertex.
Note: Sloane's A001174 asserts there are 42 digraphs on 4 vertices.
Yeah it's possible. For example take $n=6$ and each of the vertices have degree $3$. Then you can construct $K_{3,3}$ the complete bipartite graph on $6$ vertices and also another graph which isn't bipartite. The second graph can be obtained by constructing two distinct $C_3$ cycles and then connecting three pairs of vertices from distinct cycles. As both don't share a property (namely bipartivity) then they can't be isomorphic to each other.
You can find a picture of the two non-isomoprhic graphs here.
Best Answer
There is no nice formula, I’m afraid. What you want is the number of simple graphs on $n$ unlabelled vertices. For questions like this the On-Line Encyclopedia of Integer Sequences can be very helpful. I searched in on the words
unlabeled graphs, and the very first entry returned was OEIS A000088, whose header is Number of graphs on n unlabeled nodes. A quick check of the smaller numbers verifies that graphs here means simple graphs, so this is exactly what you want. It tells you that your $1,2$, and $4$ are correct, and that there are $11$ simple graphs on $4$ vertices. You should check your list to see where you’ve drawn the same graph in two different ways. If you get stuck, this picture shows all of the non-isomorphic simple graphs on $1,2,3$, or $4$ nodes. The OEIS entry also tells you how many you should get for $5$ vertices, though I can’t at the moment point you at a picture for a final check of whatever you come up with.