Directed graph isomorphism condition correctness

Question

I'm currently working on a project and I've hit a bit of a stumbling point regarding one part related to directed graph isomorphism. To put it short, I have to find all graphs with N = 1,2,3,4 vertices which aren't isomorphic to one another. Based on this entry in the online integer sequence encyclopedia, there's 1, 3, 16, 218 such graphs respectively.

I have to do this via programming, however, my question is of a mathematical nature, hence I decided to post it here rather than StackOverflow.

I've done some research/googling, and I've found that these four conditions being true indicates that two graphs are isomorphic:

1. Number of vertices is the same
2. Number of edges is the same
3. Degree sequence is the same
4. They have an equal number of circuits, and those circuits have to be of the same length (i.e. if one graph has 3 circuits with the length of 3,4,5 - then the other graph needs to have 3 circuits with the same individual lengths)

And for the most part, this felt both intuitive to me, as well as accurate on graphs with N = 1,2,3 vertices. However, when it came to 4-vertex graphs, it didn't seem to be 100% correct. When I run my algorithm on all possible 4-vertex graphs, I end up with a total of 215 graphs, in other words, I lack 3.

I managed to find the missing graphs manually, and I managed to find their counterparts in my list. I've checked these properties for each graph manually as well, to make sure my algorithm isn't wrong or something, and the result was the same - each pair did indeed have all of the 4 conditions above true.

This led me to believe that perhaps these conditions are not accurate for every given graph (at least for N >= 4 vertices). So I thought of coming here to see if these conditions are indeed wrong, or if I should revisit my entire isomorphism check algorithm and see if I made some kind of logical error there.

Answer 1

There are no such simple conditions that guarantee that two graphs are isomorphic.

If you're using a computer anyway, and the number of vertices is pretty small, then you should probably be using the definition of isomorphism:

$G,H$ are isomorphic if there is a bijection $f: V(G) \to V(H)$ such that a directed edge $(u,v)$ exists in $G$ if and only if the edge $(f(u), f(v))$ exists in $H$.

Checking the number of vertices or edges or the degree sequence is a useful preprocessing step, because if two graphs are isomorphic, then certainly these parameters, or any other parameters, must also be equal. Counting the circuits might be already more complicated than checking the definition, so I don't think it's as useful for a preprocessing step.

The indegrees and outdegrees of vertices might help you narrow down which bijections to try, instead of trying all of them (though $4!$ isn't a big number). If $f$ is an isomorphism, then it must send each vertex in $G$ to a vertex in $H$ with the same indegree and outdegree.