= Graph invariant
A \b[graph invariant] assigns a value to a <graph> in a way preserved by <graph isomorphism>. For an invariant $I$,
$$
G\cong H\quad\Longrightarrow\quad I(G)=I(H).
$$
The value may be a number, a sequence or another mathematical object whose equality has been specified. Isomorphism preserves adjacency while allowing a relabeling of vertices; a drawing's page coordinates are therefore not a graph invariant.<Discrete Mathematics: An Open Introduction (3rd edition) by Oscar Levin>[§4.1, isomorphic graphs]{ref}
Examples include vertex count, edge count, the sorted <degree sequence> and the number of <connected components of a graph>. If even one invariant differs, it proves <graph non-isomorphism>. Equality of an invariant usually supplies only a necessary condition. For example, a six-vertex <cycle graph> and two disjoint triangles both have six vertices, six edges and six degrees equal to2, but only the cycle is a <connected graph>. The example in <graph non-isomorphism> proves the obstruction through connectedness.
The <adjacency matrix> gives an algebraic way to construct invariants. Relabeling a graph replaces $A$ by $P^TAP$ for a <permutation matrix> $P$. Hence
$$
\operatorname{tr}((P^TAP)^k)=\operatorname{tr}(P^TA^kP)=\operatorname{tr}(A^k).
$$
For a finite undirected <simple graph>, the $i$th diagonal entry of $A^3$ counts three-step closed walks from vertex $i$. Every triangle gives two traversal directions and three possible starting vertices, so the number of <triangles in a graph> is
$$
t(G)=\frac16\operatorname{tr}(A^3).
$$
The six-cycle has no triangles and trace zero; two disjoint triangles have trace12 and triangle count2. This invariant distinguishes them even though their degree sequences agree.
A <complete graph invariant> would satisfy the reverse implication too: equal values would guarantee graph isomorphism. Being easy to compute and being complete are separate properties. Combining several inexpensive invariants can reject many non-isomorphic pairs, but a surviving pair still requires a justification that the chosen information determines its adjacency structure.
Back to article page
