Suppose we have two graphs, one with vertex set \({ V }\) and edge relation \({ E }\) and the other with vertex set \({ W }\) and edge relation \({ F }\). A function \({ g }\) from \({ V }\) to \({ W }\) is called a graph isomorphism if is bijective and \({ ( g ( a ) , g ( b ) ) ∈ F }\) whenever \({ ( a , b ) ∈ E }\) and vice versa. In the special case \({ W = V }\) and \({ F = E }\) it’s called an automorphism.
There is rarely much point in distinguishing between isomorphic graphs, and people often implicitly treat isomorphic graphs as equal. For example, people talk of \({ K _ n }\) as the complete graph with \({ n }\) vertices. Technically, there is such a graph for each set with \({ n }\) elements, but for purposes of graph theory they all behave the same, and so we speak as if there were only one.
An easy way to describe isomorphism, at least for finite graphs, is that two graphs are isomorphic if and only if their vertices can be ordered in such a way that they have the same adjacency matrix. Or, if we don’t want to disturb an ordering that we may already have given the vertices, they are are isomorphic if and only if one adjacency matrix can be converted into the other by applying a permutation to the rows and applying the same permutation to its columns.
Every graph has at least one automorphism, corresponding to the identity function, but even small graphs may have many more. The \({ K _ { 6 , 6 } }\) graph we just saw has a number of automorphisms which are geometrically obvious, such as rotations through any integer multiple of 30 degrees, but it has many more. We can permute the members of each group of six vertices separately. We can also rotate through 30 degrees, which switches the two groups, and then permute within each of them. There is a binary choice whether to rotate first and then \({ 6 ! = 720 }\) possible permutations within each group, for a total of \({ 2 · 720 · 720 = 1,036,800 }\) automorphisms. I won’t list them.
More generally, \({ K _ { p , q } }\) has \({ p ! · q ! }\) automorphisms, unless \({ p = q }\), in which case there are twice as many, because in that case we can not only permute each of the two subsets into which the vertices have been partitioned but can also swap the two subsets.