Title: On the Combinatorial Power of the Weisfeiler-Lehman Algorithm,
Abstract: The classical Weisfeiler-Lehman method WL[2] uses edge colors to produce a
powerful graph invariant. It is at least as powerful in its ability to
distinguish non-isomorphic graphs as the most prominent algebraic graph
invariants. It determines not only the spectrum of a graph, and the angles
between standard basis vectors and the eigenspaces, but even the angles between
projections of standard basis vectors into the eigenspaces. Here, we
investigate the combinatorial power of WL[2]. For sufficiently large k, WL[k]
determines all combinatorial properties of a graph. Many traditionally used
combinatorial invariants are determined by WL[k] for small k. We focus on two
fundamental invariants, the num- ber of cycles Cp of length p, and the number
of cliques Kp of size p. We show that WL[2] determines the number of cycles of
lengths up to 6, but not those of length 8. Also, WL[2] does not determine the
number of 4-cliques.