Abstract
The Weisfeiler-Leman (WL) graph isomorphism test is a fundamental algorithm in graph theory, known to be equivalent to comparing the number of homomorphisms from trees. While this equivalence—the Dvořák–Dell–Grohe–Rattan theorem—is well-established, existing proofs typically rely on complex logical frameworks or sophisticated linear algebra. This paper provides a fresh, intuitive proof of the theorem by introducing a linear ordering on WL-labels and employing an asymptotic argument involving sequences of trees. By showing that certain labels dominate homomorphism counts as tree size increases, the author bypasses traditional machinery to offer a purely combinatorial perspective.
Introduction
The Weisfeiler-Leman (WL) test is a cornerstone of structural graph theory and computer science, used to determine if two graphs, $G_1$ and $G_2$, are isomorphic. The test is sound but incomplete; it can distinguish many non-isomorphic graphs but fails on others, such as a single hexagon versus two disjoint triangles.
A landmark result in this field states that the $k$-level WL test can distinguish two graphs if and only if there exists some tree $T$ that has a different number of homomorphisms to $G_1$ than to $G_2$. A homomorphism is a structure-preserving map from the vertices of $T$ to the vertices of $G$. Despite the importance of this theorem, the standard proofs are notoriously dense, drawing from finite model theory or high-level linear algebra. This work seeks to simplify the "hard direction" of this proof—showing that different WL-labels imply different homomorphism counts—using basic combinatorial counting and asymptotic growth.
Methodology
The author’s innovation lies in two primary components: a lexicographical ordering of WL-labels and the construction of asymptotic tree sequences.
1. Ordering WL-Labels
The proof begins by defining a linear order for WL-labels at each iteration $k$.
- For $k=0$, all nodes receive the same initial label, and thus all labels are equal.
- For $k=1$, labels are ordered by the degree of the node.
- For higher $k$, labels are multisets of labels from the previous level ($k-1$). These are compared lexicographically: one compares the "largest" element where two multisets differ; the multiset containing more of that specific element is deemed "larger."
2. Asymptotic Tree Sequences
The core of the argument is Lemma 1, which posits that for any set of labels, one can construct a sequence of rooted trees $T_n^k$. The construction is designed such that if label $\ell_1$ is smaller than $\ell_2$ in the defined order, the number of homomorphisms from $T_n^k$ to a node with label $\ell_1$ becomes negligible compared to the count for a node with label $\ell_2$ as $n$ approaches infinity. Formally: $$h(T_n^k, \ell_1) = o(h(T_n^k, \ell_2))$$
3. The Asymptotic Proof
To prove the theorem, the author demonstrates that if two graphs $G_1$ and $G_2$ are distinguished by the WL test, they must possess a different number of nodes with the "largest" possible label at some level $k$. As the tree size $n$ in the sequence $T_n^k$ increases, the homomorphisms to nodes with this dominant label will eventually overwhelm the counts for all other labels. This ensures that the total homomorphism counts $hom(T_n^k, G_1)$ and $hom(T_n^k, G_2)$ cannot remain equal for all $n$.
Key Insights
Dominance through Growth
The "aha moment" of this research is the realization that we do not need to identify a single "perfect" tree to distinguish two graphs. Instead, by building a sequence of trees where the "value" of a higher-order label grows exponentially faster than a lower-order one, we can guarantee that the counts will eventually diverge.
Recursive Tree Construction
The proof utilizes a clever inductive construction. To build a tree for level $k+1$, the author takes a tree from level $k$ and attaches $n$ copies of it to a new root. This exponential scaling is the engine that drives the asymptotic dominance of larger labels, turning a complex multiset comparison into a clear-cut battle between the most significant labels.
Results and Implications
The paper successfully re-proves the Dvořák–Dell–Grohe–Rattan theorem: If two graphs $G_1$ and $G_2$ are distinguished by the WL test, then there exists a tree $T$ such that $hom(T, G_1) \neq hom(T, G_2)$.
While the proof is asymptotic, it is inherently constructive. It suggests that if the WL test distinguishes two graphs at level $k$, a sufficiently "wide" and "deep" tree will always reveal that difference through homomorphism counts. This provides a more intuitive bridge between the iterative coloring process of the WL test and the global structural properties of tree homomorphisms.
Limitations and Future Work
Despite its elegance, the asymptotic approach has specific limitations:
- Isolated Nodes: The primary lemma assumes graphs do not have isolated nodes, as the core argument relies on nodes having neighbors to propagate homomorphism counts. While the author provides a workaround based on total node counts, the asymptotic logic is most robust for connected components.
- Tree Size: Because the proof relies on $n \to \infty$, the resulting tree $T$ required to distinguish two graphs might be astronomically large. The paper does not provide a tight bound on the minimum size or depth of the tree needed.
- Higher-Order WL: This work focuses on the standard node-based WL test. A natural next step would be extending this asymptotic approach to the $k$-dimensional Weisfeiler-Leman test, which considers tuples of nodes rather than individual vertices.
Summary updated