Colour refinement 2026-11-05
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 be a vertex's colour after round . 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 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 with the same colour. The first round separates endpoints from internal vertices . The next separates , which each have an endpoint neighbour, from , which do not. The three cells
are 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 and the triangular prism graph remain one six-vertex cell because every vertex has three neighbours. Yet the prism has triangles and 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.
The Turan theorem states that every -vertex graph with no has at most edges, where is the complete -partite graph with part sizes differing by at most one.
Here is an induction on and . If a -free graph contains no , induction on gives
Otherwise choose a copy of . Every vertex outside has at most neighbors in , and induction on gives
The last identity is obtained by removing one vertex from every part of . This proves the theorem; the standard equality analysis forces the balanced complete -partite graph.
Now suppose is rhombus-free. If it is triangle-free, the case just proved gives
. Otherwise remove the three vertices of a triangle. No remaining vertex can be adjacent to two vertices of that triangle, since those two triangle vertices and the outside vertex would form a second triangle sharing an edge with the first. Induction therefore gives
This proves the rhombus-free edge bound and hence the requested strict contrapositive.
For equality at , take the triangular prism graph: two disjoint triangles joined by a matching. It has edges. Every edge belongs to at most one triangle, so there is no rhombus, while the presence of triangles proves that it is not isomorphic to .
Prism graph 2026-10-14
A prism graph joins two copies of a cycle graph by matching corresponding vertices. The triangular prism graph is the three-cycle case, with six vertices and nine edges.