 Graph invariant

A graph invariant assigns a value to a graph in a way preserved by graph isomorphism. For an invariant $I$,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.^[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^{T}AP$ for a permutation matrix $P$. HenceFor 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 isThe 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.