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]
Practical graph isomorphism, II by Brendan D. McKay and Adolfo Piperno. Section3.1, equitable refinement and Algorithm1
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 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 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.
Past exam of the mathematics course of the University of Cambridge 2024 ii Paper 2 17I Solution Created 2026-09-23 Updated 2026-09-25
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 givesOtherwise choose a copy of . Every vertex outside has at most neighbors in , and induction on givesThe 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 givesThis proves the rhombus-free edge bound and hence the requested strict contrapositive.
. 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 givesThis proves the rhombus-free edge bound and hence the requested strict contrapositive.
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.