 Equitable partition

An equitable partition of a finite graph groups vertices so that any two vertices in one cell have the same number of neighbours in each cell. For a simple graph with cells $C_1,\dots ,C_k$, this means that numbersdo not depend on which $v$ in $C_i$ is selected. Here $N(v)$ denotes the set of neighbours of $v$. These counts form the equitable quotient matrix $B=(b_{ij})$. An equitable partition need not be a proper vertex colouring and need not have cells of equal sizes.^[ref]

An original five-vertex path graph $1-2-3-4-5$ has an equitable partitionEach endpoint has one neighbour in $C_2$; each member of $C_2$ has one neighbour in $C_1$ and one in $C_3$; the middle vertex has two neighbours in $C_2$. Although the graph is undirected, $B$ is not symmetric matrix, because its entries count neighbours per vertex rather than total edges between cells. Counting those edges from both ends gives $|C_i|b_{ij}=|C_j|b_{ji}$.

The counts also compress an exact part of the adjacency matrix. Let $A$ be that matrix and let $S$ have one column per cell, with $S_{vi}=1$ for $v\in C_i$ and zero otherwise. ThenIndeed, $(AS{)}_{vj}$ counts neighbours of $v$ in $C_j$, which is exactly $(SB{)}_{vj}$. Hence $Bz=\lambda z$ implies $A(Sz)=\lambda (Sz)$. Since nonempty disjoint cells make the columns of $S$ linearly independent, $z\ne 0$ gives $Sz\ne 0$: every eigenvalue of $B$ is an eigenvalue of $A$. For the displayed example, these include $0$ and $\pm \sqrt{3}$.

An equitable partition preserves neighbour counts, not all adjacency information. The disjoint union of graphs of a triangle and a four-vertex cycle has an equitable one-cell partition, since every vertex has two neighbours. Nevertheless, no graph automorphism can send a triangle vertex to a four-cycle vertex: their connected components of a graph are not isomorphic. This distinguishes equitable cells from symmetry orbits and explains why colour refinement may leave ambiguity.