= Complete graph invariant
A \b[complete graph invariant] is a <graph invariant> whose value determines a graph up to <graph isomorphism>. For graphs in a specified class, completeness means
$$
I(G)=I(H)\quad\Longleftrightarrow\quad G\cong H.
$$
An ordinary invariant only requires the forward preservation statement $G\cong H\Rightarrow I(G)=I(H)$. Completeness adds the converse: equal values must exclude <graph non-isomorphism>.
A direct construction proves that complete invariants exist for finite undirected <simple graphs>. For an $n$-vertex graph, label its vertices $1,\ldots,n$ and list the entries above the diagonal of its <adjacency matrix> in the fixed order $(1,2),(1,3),\ldots,(n-1,n)$. This gives a binary string. Repeat for every labeling and choose the least string in <lexicographic order>. Define $I(G)$ to be the pair consisting of $n$ and this least string. Including $n$ distinguishes graphs whose edge string is empty but whose vertex counts differ.
Relabeling a graph permutes the same collection of candidate strings, so isomorphic graphs have the same minimum. Conversely, if two minima and vertex counts agree, some labeling of each graph gives exactly the same adjacency entries. Matching vertices with those labels is an isomorphism. This proves both directions, without assuming that the construction is computationally fast.
For an original three-vertex example, a path's possible strings are $011$, $101$ and $110$ in the order $(12,13,23)$. Its invariant is $(3,011)$. A triangle instead gives $(3,111)$. The difference certifies non-isomorphism. For larger graphs the naive construction may examine $n!$ labelings, so mathematical completeness alone supplies no practical speed guarantee.
<Canonical graph labeling> produces a standardized labeled representative and is closely connected to this construction. The authors of nauty and Traces identify canonical-label production as one of their programs' tasks.<nauty and Traces by Brendan McKay and Adolfo Piperno>[project overview and Documentation]{ref} A particular program's chosen representative need not be the lexicographically least string used in this illustrative definition; comparisons must use the same canonization convention.
Vertex count, edge count and <degree sequence> are useful inexpensive invariants but are not complete. The example in <graph non-isomorphism> gives equal values for all three while connectedness differs. Completeness concerns the information retained, separately from the effort required to compute it.
Back to article page
