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 homomorphism \({ ( g ( a ) , g ( b ) ) ∈ F }\) whenever \({ ( a , b ) ∈ E }\).
Several concepts we’ve already defined can be expressed in terms of homomorphisms. For example, a graph \({ E }\) is bipartite if and only if there is a homomorphism \({ g }\) from it to a complete graph with two vertices, which we’ll call \({ u }\) and \({ v }\), since we can partition the vertices \({ E }\) into those for which \({ g ( a ) = u }\) and those for which \({ g ( a ) = v }\). The definition of a homomorphism and the fact that complete graphs have no self-loops imply that there are no edges between a vertex in the first set and a vertex in the second set. More generally, a graph has an \({ m }\)-colouring if and only if there is a homomorphism from it to a complete graph with \({ m }\) vertices.
A graph homomorphism is called a graph isomorphism if it is a bijective function and its inverse is also a homomorphism. In other \({ g }\) from \({ V }\) to \({ W }\) is an 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. \({ K _ n }\) has \({ n ! }\) automorphisms, since any bijective function from the set of vertices to itself will be an automorphism. \({ 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. The graph we saw earlier, with vertices labelled \({ 0 }\) to \({ 13 }\), has 336 automorphisms. Our first two examples of graphs, by contrast, have only the identity automorphism.