Finding Graph Isomorphisms?

Question

I'm still a bit confused about all the ways to find if two graphs are isomorphic. There's drawing the complement, just brute forcing it by counting vertices & edges and trying to match the two, and through cycles and circuits? I'm still a bit confused on how counting cycles and circuits can help you tell if two graphs are isomorphic and I was just wondering what other ways are there that I haven't listed? Thanks guys.

Answer 1

Spoiler: For a more detailed answer, check https://math.stackexchange.com/a/2486945/509159 Also generally check out https://en.wikipedia.org/wiki/Graph_isomorphism_problem

As pointed out in the comments, there is currently no efficient way known to check if two different arbitrary graphs are isomorphic. There are however, two other tricks:

1. If the graphs are not arbitrary but known to belong to one of certain graph families, then it is possible to efficiently check them for isomorphism.
2. Graph invariants are defined as properties of graphs that are preserved under isomorphisms, so if the two graphs have at least one different graph invariant, they cannot be the same.

Some graph families that fall into (1.) are trees and planar graphs, but also more abstract properties like graphs with bounded degree.

Most graph invariants come from the property (or rather, definition), that isomorphisms between graphs preserve adjacency. E.g. if the first graph is connected and the two graphs are isomorph, then the second graph must be connected, too. Note that this doesn't imply that any two connected graphs are isomorph. So in general no matter how many graph invariants we know to be same, we cannot infer that the two graphs are isomorphic (though for special sets of graph invariants, this is enough, see below). The invariant not coming from preserving the adjacency is that the two graphs must have the same number of vertices, since isomorphisms between graphs are bijections between the vertex sets. With the adjacency preservation we can conclude that the number of edges must be the same, too.

Examples:

1. Any two path graphs can be shown to be isomorphic or not by counting their vertices.
2. The path graph and cycle graph with $n$ vertices each cannot be isomorphic because the cycle graph has one edge more (note that the invariants of number of vertices and connectedness are the same nevertheless).
3. Two graphs with the same number of vertices and no edges are always isomorphic (there is no adjacency to preserve).
4. Two connected 2-regular graphs with countable infinite many vertices are always isomorphic. This graph is called double-ray.
5. There is a model of random graphs on a countable infinite set of vertices such that every such graph is isomorphic to any other. This graph is called the Rado graph.

Conclusion: So unless you know anything useful about the two graphs, there is no efficient way to determine if both are isomorphic.