On the Expressive Power of Implicit Line-Graph Higher-Order Weisfeiler--Leman

Whitney's theorem allows isomorphism testing for connected simple graphs, apart from K 3 and K 1,3, to be formulated as distinguishing their line graphs. However, the relation between fixed-dimensional Weisfeiler--Leman (WL) expressivity on line graphs and on their roots remains unresolved. We study this relation through Implicit Line-Graph WL (ILG- k-WL), which is exactly k-WL on L(G), executed over the edges of G with line-graph relations derived from endpoint incidence and without explicitly constructing L(G). On the Whitney-general class, the relation between root-domain and line-graph WL depends on k. For k=1,2, ILG- k-WL adds no distinguishing power beyond root-domain 1-WL and misses some pairs that 1-WL separates. For k=3, we prove the backward containment L(G) 3-WLL(H) so G 3-WLH. Strongly regular witness pairs, including the Shrikhande/rook pair, show that ILG- 3-WL is strictly more expressive than 3-WL. The backward containment also extends to disconnected graphs with no isolated vertices when every connected component is Whitney-general. Deterministic ILG- 3-WL separates all three substructure-counting witness pairs, all 105 pairs in SR25, and 359 of 400 BREC pairs. An untrained dense ILG- 3-GNN gives the same pairwise verdicts on these evaluations.