Chapter 14. Graph Invariants
Chapter 14. Graph Invariants
A graph invariant is a quantity or property that depends only on the structure of a graph, not on the names of its vertices, the order in which the vertices are listed, or the way the graph is drawn. If two graphs are isomorphic, then every graph invariant has the same value on both graphs. This is the defining idea: graph invariants are preserved under isomorphism.
Graph invariants are used to describe graphs, compare graphs, rule out isomorphism, state theorems, and organize graph classes. They are not usually enough to determine a graph completely, but they give compact structural information.
14.1 Definition
Let (\mathcal{G}) be a class of graphs. A graph invariant is a function
$$ I : \mathcal{G} \to X $$
such that whenever
$$ G \cong H, $$
we have
$$ I(G)=I(H). $$
Here (X) may be a set of numbers, sequences, polynomials, matrices up to equivalence, or truth values.
For example:
| Invariant | Value type |
|---|---|
| Number of vertices | Integer |
| Number of edges | Integer |
| Degree sequence | Sequence of integers |
| Chromatic number | Integer |
| Connectedness | Truth value |
| Characteristic polynomial | Polynomial |
| Spectrum | Multiset of eigenvalues |
A graph property is often a Boolean invariant. It answers yes or no. For example, “is connected,” “is bipartite,” and “is planar” are graph properties.
14.2 Isomorphism and Invariance
Graph invariants are tied to isomorphism.
If
$$ G \cong H, $$
then (G) and (H) have the same abstract structure. Their vertices may have different names, and their drawings may look different, but their adjacency pattern is the same.
An invariant must ignore superficial representation.
For example, suppose (G) has vertices
$$ {a,b,c} $$
and edges
$$ {{a,b},{b,c}}. $$
Let (H) have vertices
$$ {1,2,3} $$
and edges
$$ {{1,2},{2,3}}. $$
These graphs are isomorphic. Both are paths on three vertices. Therefore they have the same order, size, degree sequence, diameter, chromatic number, and number of components.
14.3 Order and Size
The simplest graph invariants are order and size.
The order of a graph is
$$ |V(G)|. $$
The size of a graph is
$$ |E(G)|. $$
If two graphs are isomorphic, their vertex sets have the same cardinality and their edge sets have the same cardinality. Hence order and size are invariants.
These invariants are weak but useful. If two graphs have different order or different size, they cannot be isomorphic.
For example, a graph with (5) vertices cannot be isomorphic to a graph with (6) vertices. A graph with (7) edges cannot be isomorphic to a graph with (8) edges.
14.4 Degree Sequence
The degree sequence of a finite graph is the list of vertex degrees, usually sorted in nonincreasing order.
If the degrees are
$$ 1,3,2,2,0, $$
then the degree sequence is
$$ (3,2,2,1,0). $$
The degree sequence is a graph invariant. An isomorphism preserves adjacency and incidence, so it preserves the degree of each corresponding vertex.
If two graphs have different degree sequences, they cannot be isomorphic.
The converse does not hold. Two non-isomorphic graphs may have the same degree sequence.
For example, a cycle of length (6) and the disjoint union of two triangles both have degree sequence
$$ (2,2,2,2,2,2), $$
but one graph is connected and the other is disconnected.
14.5 Connectedness and Number of Components
Connectedness is a graph property. It is invariant under isomorphism.
If (G) is connected and (G \cong H), then (H) is connected. An isomorphism maps paths in (G) to paths in (H).
The number of connected components is also an invariant:
$$ c(G). $$
If two graphs have different numbers of components, they cannot be isomorphic.
For example:
| Graph | Number of components |
|---|---|
| Path (P_5) | 1 |
| Cycle (C_5) | 1 |
| Empty graph on (5) vertices | 5 |
| Disjoint union (K_3 \cup K_2) | 2 |
The invariant (c(G)) gives global information that the degree sequence may miss.
14.6 Distance Invariants
Distances give several graph invariants.
For a connected graph, the distance between vertices (u) and (v) is
$$ d(u,v), $$
the length of a shortest path between them.
From distances, one obtains:
| Invariant | Definition |
|---|---|
| Diameter | (\max_{u,v} d(u,v)) |
| Radius | (\min_v \max_u d(v,u)) |
| Eccentricity multiset | Multiset of all vertex eccentricities |
| Wiener index | Sum of distances over unordered vertex pairs |
The diameter of (P_n) is
$$ n-1. $$
The diameter of (K_n), for (n \geq 2), is
$$ 1. $$
Distance invariants describe how spread out a connected graph is.
14.7 Cycle Invariants
Cycle structure gives important invariants.
The girth of a graph is the length of its shortest cycle. If the graph has no cycles, the girth is often taken to be (\infty).
The circumference is the length of its longest cycle, when such a cycle exists.
The cycle rank, or cyclomatic number, is
$$ |E(G)|-|V(G)|+c(G). $$
For a connected graph, this becomes
$$ |E(G)|-|V(G)|+1. $$
This number measures how many independent cycles the graph contains.
For a tree with (n) vertices and (n-1) edges,
$$ |E|-|V|+1 = (n-1)-n+1 = 0. $$
Thus trees have cycle rank (0).
14.8 Planarity
Planarity is a graph invariant.
A graph is planar if it can be drawn in the plane without edge crossings. If (G) is planar and (H\cong G), then (H) is also planar, because the same abstract adjacency structure can be drawn in the same crossing-free way after relabeling.
Planarity is a property, rather than a numerical invariant.
Examples:
| Graph | Planar? |
|---|---|
| (K_4) | Yes |
| (K_5) | No |
| (K_{3,3}) | No |
| Any tree | Yes |
| Any cycle | Yes |
Planarity depends on the existence of some crossing-free drawing, not on a particular drawing. A graph may be drawn with crossings even when it is planar.
14.9 Bipartiteness
Bipartiteness is another graph property.
A graph is bipartite if its vertex set can be partitioned into two sets
$$ A $$
and
$$ B $$
so that every edge has one endpoint in (A) and one endpoint in (B).
Bipartiteness is invariant under isomorphism. Relabeling vertices does not change whether such a partition exists.
A graph is bipartite if and only if it has no odd cycle.
Thus the property can be detected through cycle structure.
Examples:
| Graph | Bipartite? |
|---|---|
| (P_n) | Yes |
| (C_n) with (n) even | Yes |
| (C_n) with (n) odd | No |
| (K_{m,n}) | Yes |
| (K_3) | No |
14.10 Chromatic Number
The chromatic number of a graph (G), written
$$ \chi(G), $$
is the minimum number of colors needed to color the vertices so that adjacent vertices receive different colors.
The chromatic number is a graph invariant. If two graphs are isomorphic, a valid coloring of one transfers to a valid coloring of the other.
Examples:
| Graph | Chromatic number |
|---|---|
| Empty graph on (n) vertices | 1 |
| (K_n) | (n) |
| Bipartite graph with at least one edge | 2 |
| Odd cycle | 3 |
| Even cycle | 2 |
The chromatic number is often hard to compute, but it is structurally important.
14.11 Clique Number and Independence Number
The clique number of (G), written
$$ \omega(G), $$
is the largest number of vertices in a clique of (G).
The independence number, written
$$ \alpha(G), $$
is the largest number of vertices in an independent set of (G).
Both are graph invariants.
Complementation exchanges them:
$$ \omega(G)=\alpha(\overline{G}) $$
and
$$ \alpha(G)=\omega(\overline{G}). $$
These invariants measure two opposite kinds of structure: complete adjacency and complete non-adjacency.
14.12 Matching and Covering Invariants
Matchings and covers also define invariants.
A matching is a set of edges no two of which share an endpoint. The matching number is
$$ \nu(G), $$
the maximum size of a matching.
A vertex cover is a set of vertices that meets every edge. The vertex cover number is
$$ \tau(G), $$
the minimum size of a vertex cover.
Both quantities are preserved under isomorphism.
For bipartite graphs, these two invariants are connected by König's theorem:
$$ \nu(G)=\tau(G). $$
For general graphs, they may differ.
14.13 Algebraic Invariants
Matrices associated with a graph produce algebraic invariants.
The adjacency matrix (A(G)), the Laplacian matrix (L(G)), and the signless Laplacian matrix are examples. Since a relabeling of vertices permutes rows and columns, quantities unchanged under simultaneous row-column permutation are graph invariants.
Important algebraic invariants include:
| Invariant | Source |
|---|---|
| Adjacency spectrum | Eigenvalues of (A(G)) |
| Laplacian spectrum | Eigenvalues of (L(G)) |
| Characteristic polynomial | (\det(\lambda I-A)) |
| Number of spanning trees | Laplacian cofactors |
| Algebraic connectivity | Second-smallest Laplacian eigenvalue |
Algebraic invariants are central in spectral graph theory, network analysis, chemistry, and combinatorial optimization.
14.14 Polynomial Invariants
Some graph invariants are polynomials.
The chromatic polynomial (P_G(k)) counts the number of proper vertex colorings of (G) using (k) colors.
The Tutte polynomial is a more general invariant that encodes several other graph quantities.
Polynomial invariants can contain more information than a single number. Their values may specialize to count colorings, flows, spanning trees, connected subgraphs, or other structures.
However, polynomial invariants are not usually complete. Non-isomorphic graphs may have the same chromatic polynomial or the same Tutte polynomial.
14.15 Complete Invariants
A graph invariant (I) is complete if
$$ I(G)=I(H) $$
implies
$$ G \cong H. $$
A complete invariant distinguishes every pair of non-isomorphic graphs.
Most familiar invariants are not complete. Order and size are not complete. Degree sequence is not complete. Spectrum is not complete. Chromatic polynomial is not complete.
A canonical labeled form of a graph can be viewed as a complete invariant, but computing such a form efficiently is closely related to the graph isomorphism problem. In general, easily computable invariants help rule out isomorphism, but equal invariant values do not prove isomorphism.
14.16 Using Invariants to Disprove Isomorphism
Graph invariants are often used negatively.
If two graphs differ in any invariant, then they are not isomorphic.
For example, suppose (G) and (H) both have six vertices and seven edges. These two invariants do not distinguish them.
Now suppose the degree sequences are
$$ (4,3,3,2,1,1) $$
and
$$ (3,3,3,3,1,1). $$
The degree sequences differ, so
$$ G \not\cong H. $$
No further comparison is needed.
This is the common practical use of invariants: they quickly eliminate impossible isomorphisms.
14.17 Equal Invariants Do Not Prove Isomorphism
Equal invariants give evidence, but not proof, unless the invariant is complete.
For example, two graphs may have the same:
$$ |V|, \qquad |E|, \qquad \text{degree sequence}, \qquad c(G), $$
and still fail to be isomorphic.
Consider:
- The cycle (C_6).
- The disjoint union (C_3 \cup C_3).
They have the same order and size:
$$ |V|=6, \qquad |E|=6. $$
They also have the same degree sequence:
$$ (2,2,2,2,2,2). $$
But they have different component counts:
$$ c(C_6)=1, \qquad c(C_3\cup C_3)=2. $$
Adding the component count distinguishes them. Yet in other cases, many common invariants may still agree.
14.18 Invariants Under Operations
Graph operations affect invariants in predictable ways.
For disjoint union,
$$ |V(G\cup H)|=|V(G)|+|V(H)| $$
and
$$ |E(G\cup H)|=|E(G)|+|E(H)| $$
when the graphs are vertex-disjoint.
The number of components satisfies
$$ c(G\cup H)=c(G)+c(H). $$
The chromatic number satisfies
$$ \chi(G\cup H)=\max(\chi(G),\chi(H)). $$
For complements,
$$ \deg_{\overline{G}}(v)=|V(G)|-1-\deg_G(v). $$
Understanding how invariants change under operations allows one to build examples and prove structural results.
14.19 Example
Let (G) be the graph with
$$ V={a,b,c,d} $$
and
$$ E={{a,b},{b,c},{c,d}}. $$
Then (G=P_4).
Its order is
$$ 4. $$
Its size is
$$ 3. $$
Its degree sequence is
$$ (2,2,1,1). $$
It is connected, so
$$ c(G)=1. $$
Its diameter is
$$ 3. $$
It is bipartite, so
$$ \chi(G)=2. $$
It has no cycle, so its girth is
$$ \infty $$
under the usual convention for acyclic graphs.
Its clique number is
$$ 2, $$
because it has edges but no triangles.
Its independence number is
$$ 2. $$
These values do not merely describe one drawing of the path. They describe the abstract graph (P_4).
14.20 Summary
A graph invariant is a value or property preserved by graph isomorphism. It depends on the abstract adjacency structure, not on labels or drawings.
Basic invariants include order, size, degree sequence, component count, diameter, girth, chromatic number, clique number, independence number, matching number, spectra, and graph polynomials.
Invariants are essential tools for comparison. If two graphs differ in any invariant, they cannot be isomorphic. If many invariants agree, the graphs may still be non-isomorphic unless the invariant used is complete. Graph theory uses invariants to classify graphs, state theorems, design algorithms, and expose structure.