On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties

1 Introduction

• Color refinement initializes vertices by degree and refines colors using neighborhood colors; 1-WL is this routine, while 2-WL is the original pair-coloring algorithm.The paper situates these algorithms within graph isomorphism testing and notes their role in practical algorithms.Source: §1 · pp. 1–2
• The paper asks how k-WL invariance relates to subgraph-pattern counts and occurrence, distinguishing count-invariant patterns C(k) from occurrence-invariant patterns R(k), with C(k) ⊆ R(k).The motivation includes subgraph frequencies used in graph-similarity testing and the significance of k-WL for isomorphism testing and logic.Source: §1 · pp. 2–3, Our results · p. 3

Our results

• For 1-WL, C(1) consists, up to isolated vertices, of stars and 2K2, while R(1) adds exactly P3 + P2, P3 + 2P2, and 2P3.Every count-invariant pattern has a count determined by the degree sequence.Source: Our results · p. 4
• For 2-WL, the matching graphs sK2 have invariant subgraph counts exactly when s ≤ 5, extending the matching-polynomial result from strongly regular graphs to all 2-WL-equivalent graphs.The extension is tight and cannot be extended to larger s.Source: Our results · p. 4
• C7 is the largest cycle in C(2), and C(2) contains P1 through P7 but no other path graphs.More generally, 2-WL-equivalent G and H have equal counts of Cs for 3 ≤ s ≤ 2g(G) + 1; neither the factor 2 nor the additive 1 can be improved.Source: Our results · p. 4
• For 2-WL occurrence invariance, R(2) excludes every graph with a unique 4-clique, and contains only finitely many cycle graphs.For every k, R(k) contains only finitely many cycle graphs; the broader conjecture that R(2) excludes all graphs with clique number above 3 remains a conjecture.Source: Our results · pp. 4–5

2 Color refinement invariance

• Up to isolated vertices, R(1) consists of the stars, 2K2, and exactly P3 + P2, P3 + 2P2, and 2P3.For the P3 + 2P2-free case, the amenability argument has exceptions 2C3 and C6; both are handled because their six vertices cannot contain P3 + 2P2.Source: §2 · p. 6, §2.3 · p. 7

2.1 Membership in C(1)

• Up to isolated vertices, C(1) consists exactly of the stars K1,s for s ≥1 and the 2-matching 2K2.The section relates star counts to the degree sequence and derives 2K2 counts by separating pairs of edges into disjoint or adjacent pairs.Source: §2 · p. 6, §2.1 · pp. 6–7

2.2 Non-membership in C(1)

• For each of P3 + P2, 2P3, and P3 + 2P2, the section uses 1-WL-equivalent witness graphs with differing occurrence to establish non-membership in C(1).The table caption specifies that each witness pair has the same number of vertices and the same degree.Source: §2.2 · p. 7, Table 1 · p. 7

2.3 Membership in R(1)

• Every (P3 + P2)-free or 2P3-free graph is amenable, while every P3 + 2P2-free graph is amenable except 2C3 and C6.Amenable means color refinement distinguishes the graph from every nonisomorphic graph; the two exceptions still satisfy the needed occurrence-invariance implication because they have six vertices.Source: §2.3 · p. 7

2.4 Non-membership in R(1)

• R(1) contains only forests of stars, and the section excludes every star forest outside its classified list using basic counterexamples and two reduction rules.The rules remove a component or cut one leaf from each component; repeated reductions reach a basic star forest already shown not to belong to R(1).Source: §2.4 · pp. 8–10

Subgraph counts

• For every k, C(k) contains patterns with htw(F)≤k; C(1) consists exactly of stars and 2K2, up to isolated vertices.Here htw is the maximum treewidth among homomorphic images of the pattern graph.Source: §3 · p. 12
• htw(F)>2 if and only if some partition of V(F) has quotient graph isomorphic to K4.Source: §3 · p. 12
• C(2) contains exactly matchings through 5K2, cycles C3–C7, and paths P1–P7 within those respective graph families.The theorem states there are no other matching, cycle, or path graphs in C(2).Source: §3 · p. 13

Cycle counts

• G and H have equal girth and equal subgraph counts, sub(Cs, G) = sub(Cs, H), for each 3 ≤ s ≤ 2g(G) + 1.Source: §3 · p. 15

Occurrence properties

• For each k, R(k) contains only finitely many cycle graphs; this follows in part because no R(k) contains all path graphs.A first-order reduction from graph isomorphism to Long Path establishes the path non-invariance used in the argument.Source: §3 · pp. 16–17
• No graph containing a unique 4-clique belongs to R(2).Source: §3 · p. 17

3 Weisfeiler-Leman invariance

• Cloning vertices into same-color copies preserves 2-WL indistinguishability when Duplicator transfers a winning 3-pebble bijection strategy.The projection from clones to original vertices lets Duplicator simulate the game on the original graphs.Source: §3 · pp. 18–19
• The constructed graphs G′ and H′ are 2-WL-equivalent, yet G′ contains F while H′ contains no copy of F.The construction assumes F contains exactly one K4; it attaches F′ to the cloned vertices according to their colors.Source: §3 · pp. 19–20

4 Concluding discussion

• The complete-description question for C(k) remains open generally, although Theorem 2.3 answers it affirmatively for k=1 and completely describes R(1).For R(2), whether matching graphs sK2 occur for only finitely many s or for all s remains unknown.Source: §4 · p. 20
• The parameter htw(F) governs both k-WL invariance of sub(F,G) and a cited algorithm's running-time exponent, suggesting a connection between invariance and algorithmics.The paper identifies this connection as an area for further exploration.Source: §4 · p. 20
• The invariance of induced subgraphs and their counts for different k remains a topic for further study.The passage notes prior study of induced-subgraph counts in finite model theory.Source: §4 · p. 20

A Proof of Lemma 2.4

• The proof splits Lemma 2.4 into Lemmas A.5, A.9, and A.8, using explicit characterizations of F-free graphs for three choices of F.The patterns are P3 + P2, P3 + 2P2, and 2P3.Source: A Proof of Lemma 2.4 · p. 24

A.1 Forbidden forests

• For v(H)≥6, H is 3P2-free exactly when its line graph has a clique cover of size at most 2.The appendix also characterizes 3P2-free graphs up to isolated vertices using specified structural families.Source: §A.1 · p. 24
• Up to isolated vertices, 3P2-free graphs are subgraphs of 2K3, K1∗(K3+sK1), or K2∗sK1 for the stated ranges of s.K2∗sK1 is a complete split graph with a clique part of size 2.Source: §A.1 · pp. 24–25
• The six-vertex threshold in the line-graph criterion is necessary: the complement of P3 + 2K1 is 3-matching-free but has line-graph clique cover number 3.Thus the criterion does not extend to all smaller graphs.Source: §A.1 · p. 25
• For 2P3-free graphs, the listed cases include a six-vertex net plus isolated edges and subgraphs of K1∗sK2.The latter family is also known as friendship graphs.Source: §A.1 · p. 27
• For a connected (P3 + P2)-free graph with at least five vertices and no isolated vertices, the proof forces a star K1,s.The proof rules out maximum degree 2 and shows all external vertices must be adjacent to the 3-star's center.Source: §A.1 · p. 27
• For connected (P3 + 2P2)-free graphs with at least seven vertices, the characterization places H as a subgraph of K1∗(K3+sK1) or K2∗sK1.The proof derives this case from the 3P2-free characterization.Source: §A.1 · p. 28
• In the connected 2P3-free proof, a tree's diameter is at most 4, and the diameter-4 case is a subgraph of a windmill graph K1∗sK2.A longer diameter would contain a P6 and hence a 2P3.Source: §A.1 · pp. 28–29
• A graph has vertex cover number at most 2 exactly when it is a subgraph of K2∗sK1 for some s≥1.Source: §A.1 · p. 29

• Every (P3 + P2)-free graph is amenable, and H + K is amenable for a forest K exactly when H is amenable.Source: §A.2 · p. 29
• In the proof for the vertex-cover case, stable color cells and their bipartite connections let a cell-preserving bijection yield an isomorphism.When the two exclusive-neighbor sets have equal size, the proof separately matches the two-star structure between cells.Source: §A.2 · pp. 30–31
• Every 3P2-free graph is amenable except 2C3.The proof reduces the remaining cases to subgraphs of K1 ∗ (K3 + sK1).Source: §A.2 · p. 31
• For 3P2-free graphs, the proof handles large pendant-vertex sets by checking that cell-respecting bijections preserve the graph.If one of the three non-pendant vertices becomes pendant, it joins the pendant cell and the same argument applies.Source: §A.2 · p. 31
• Every (P3 + 2P2)-free graph is amenable except 2C3 and C6.Source: §A.2 · p. 31
• Every 2P3-free graph is amenable.For windmill subgraphs, the proof uses stable color cells and shows that the within-cell and between-cell structures are determined up to isomorphism.Source: §A.2 · pp. 31–32