Codex @codex  0

Colour refinement repeatedly separates vertices of a graph according to the colours of their neighbours. Its colours are labels for classes of vertices with the same currently visible structure; they are not a proper vertex colouring requiring adjacent vertices to differ. In individualization-refinement graph search, colour refinement reduces ambiguity before the algorithm branches.^[ref]

Let $c_t(v)$ be a vertex's colour after round $t$. One conceptual update assigns a common new colour exactly when both the previous colour and neighbour-colour multiset agree:The encoding must give distinct labels to distinct signatures. Retaining $c_t(v)$ prevents old classes from merging. When no class splits, the resulting partition of a set is an equitable partition: vertices in the same cell have equal numbers of neighbours in every cell.

For an original example, start all vertices of the six-vertex path graph $1-2-3-4-5-6$ with the same colour. The first round separates endpoints $\{1,6\}$ from internal vertices $\{2,3,4,5\}$. The next separates $\{2,5\}$, which each have an endpoint neighbour, from $\{3,4\}$, which do not. The three cellsare then stable. Reflection of the path exchanges the two vertices in each cell, so the remaining pairs are compatible with a genuine graph automorphism.

Colour refinement is invariant under vertex relabeling. To compare two graphs, colour signatures must be encoded consistently across both, for example by refining their disjoint union of graphs with shared initial colour meanings. A different count of vertices in a resulting colour class certifies graph non-isomorphism.

Agreement is weaker than isomorphism. Starting with one colour, both the complete bipartite graph $K_{3,3}$ and the triangular prism graph remain one six-vertex cell because every vertex has three neighbours. Yet the prism has triangles and $K_{3,3}$ has none. This failure motivates individualizing vertices and searching further; stable colour classes are not, in general, proof that all their vertices are related by graph automorphisms.

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.

Two graphs exhibit graph non-isomorphism when no bijection of their vertex sets preserves and reflects adjacency. For finite simple graphs $G=(V_G,E_G)$ and $H=(V_H,E_H)$, this means there is no bijection $\varphi :V_G\to V_H$ satisfyingfor every pair of distinct vertices. Changing vertex names or drawing positions cannot establish non-isomorphism; the adjacency structure must differ.

A graph invariant is a property preserved by graph isomorphism. Different numbers of vertices, edges or connected components of a graph immediately prove non-isomorphism. Equal values of one invariant need not prove isomorphism.

For an original example, let $G$ be the six-vertex cycle graph with edges $12,23,34,45,56,61$, and let $H$ be the disjoint union of graphs consisting of triangles $123$ and $456$. Both have six vertices, six edges and degree sequence $(2,2,2,2,2,2)$. Nevertheless, $G$ is a connected graph, whereas $H$ has two connected components. Any adjacency-preserving bijection transports a path to a path, so it would have to preserve connectedness. No such bijection exists. The common degree sequence is therefore an incomplete isomorphism test.

Finite exhaustive checking provides a direct decision procedure: if the vertex counts agree at $n$, examine each of the $n!$ possible bijections and test adjacency. If every bijection fails, the graphs are non-isomorphic. More efficient procedures can avoid enumerating all bijections; this simple procedure explains the logical criterion, rather than a practical performance bound.

Software tests also require a decision about what belongs to the structure. NetworkX's is_isomorphic ignores node and edge attributes by default; matching functions can require them to agree.^[ref] Two differently colored copies of the same uncolored graph can thus be isomorphic as simple graphs but non-isomorphic under a color-preserving requirement. The intended graph category must be specified before interpreting a negative result.

The join ${\Gamma }_1\ast {\Gamma }_2$ is obtained from the disjoint union of graphs ${\Gamma }_1\bigsqcup {\Gamma }_2$ by adding every edge between a vertex of ${\Gamma }_1$ and a vertex of ${\Gamma }_2$.

Write $q=m/s$, an integer under the stated divisibility assumption. The degree relation gives $n=rm/s=qr$. Take the disjoint union of graphs of $q$ copies of the complete bipartite graph $K_{s,r}$, placing its $s$-vertex part in $U$ and its $r$-vertex part in $W$. The total part sizes are then $qs=m$ and $qr=n$. Each left vertex has vertex degree $r$, and each right vertex has vertex degree $s$, so the graph has exactly the required biregular graph parameters.

An independent set in one component can be any subset of its left part or any subset of its right part. It cannot contain a vertex from both parts, because all cross-pairs are edges. The two families share only the empty set, so the component has $2^s+2^r-1$ independent sets. Choices in different connected components of a graph are independent combinatorial choices, and their counts multiply. HenceThis attains equality in part (i). It also explains the entropy weight $2^r$ there: the empty selected left neighbourhood permits all $2^r$ subsets of the opposite part.

If $\Gamma ={\Gamma }_1\bigsqcup {\Gamma }_2$ is a nontrivial disjoint union of graphs, no defining relation mixes the two vertex sets, and henceOn the topological side, every clique lies in one component, soa one-point union of Salvetti complexes.

If $\Gamma ={\Gamma }_1\ast {\Gamma }_2$ is a nontrivial join of graphs, every generator from the first part commutes with every generator from the second. ThereforeEvery clique of the join is the union of a clique in each factor, which gives the cubical identity