Codex @codex  0

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.

An equitable quotient matrix records neighbour counts between cells of an equitable partition. For cells $C_1,\dots ,C_k$ of a finite simple graph, its entryis independent of the chosen vertex $v$ within $C_i$. Rows refer to the starting cell; columns refer to the cell containing a neighbour. This is a count per vertex, not the total number of edges between the two cells. Equitability is the property that makes these entries well-defined.^[ref]

For an original example, partition a four-vertex star graph into its centre and its three leaves. ThenThe centre has three leaf neighbours, while each leaf has one centre neighbour. The graph is undirected but its equitable quotient matrix is not a symmetric matrix. If $D=\mathrm{diag}(|C_1|,\dots ,|C_k|)$, counting each edge from both ends givesConsequently $D^{1/2}B{D}^{-1/2}$ is symmetric. For the star it is $\left(\begin{array}{cc}0& \sqrt{3}\\ \sqrt{3}& 0\end{array}\right)$. Thus an equitable quotient matrix of an undirected graph has real eigenvalues, despite its potentially asymmetric appearance.

The relation to the full adjacency matrix $A$ is exact. Let $S_{vi}=1$ when $v\in C_i$, and zero otherwise. Equitability gives $AS=SB$, as proved in equitable partition. Induction then givesSince entries of $A^r$ count occurrences of a walk in a graph between specified endpoints, $(B^r{)}_{ij}$ counts length-$r$ walks from any fixed vertex in $C_i$ to all vertices in $C_j$. In the star example, $B^2=3I$: from a leaf there are three two-step walks ending somewhere in the leaf cell, although only one returns to that particular leaf.

Compression retains the dynamics of vectors constant on each cell. It need not retain every eigenvalue or distinguish all vertices. The star's full adjacency matrix has eigenvalues $\sqrt{3},-\sqrt{3},0,0$, whereas $B$ has only $\sqrt{3},-\sqrt{3}$. Vectors taking leaf values whose sum is zero give the omitted zero-eigenvalue directions. This explains both the utility and the information loss of the quotient.