{'fraction_non_alphanumeric': 0.068437247385851, 'fraction_numerical': 0.01654541187514668, 'mean_word_length': 3.334991239473238, 'pattern_counts': {'":': 0, '<': 16, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 52, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs

The Weisfeiler-Leman procedure is a widely-used technique for graph isomorphism testing that works by iteratively computing an isomorphism-invariant coloring of vertex tuples. Meanwhile, a fundamental tool in structural graph theory, which is often exploited in approaches to tackle the graph isomorphism problem, is the decomposition into 2- and 3-connected components. We prove that the 2-dimensional Weisfeiler-Leman algorithm implicitly computes the decomposition of a graph into its 3-connected components. This implies that the dimension of the algorithm needed to distinguish two given non-isomorphic graphs is at most the dimension required to distinguish non-isomorphic 3-connected components of the graphs (assuming dimension at least 2). To obtain our decomposition result, we show that, for k>= 2, the k-dimensional algorithm distinguishes k-separators, i.e., k-tuples of vertices that separate the graph, from other vertex k-tuples. As a byproduct, we also obtain insights about the connectivity of constituent graphs of association schemes. In an application of the results, we show the new upper bound of k on the Weisfeiler-Leman dimension of the class of graphs of treewidth at most k. Using a construction by Cai, F\"urer, and Immerman, we also provide a new lower bound that is asymptotically tight up to a factor of 2.


Introduction
Originally introduced in [41], the Weisfeiler-Leman (WL) algorithm has become a -if not the -fundamental combinatorial subroutine in the context of isomorphism testing for graphs. It is used both in theoretical and in practical approaches to tackle the graph isomorphism problem (see, e.g., [5,20,34,35,38]), among them is also Babai's recent quasipolynomial-time isomorphism test [4]. For every k ≥ 1, there is a k-dimensional version of the algorithm (k-WL) which colors the vertex k-tuples of the input graph and iteratively refines the coloring in an isomorphism-invariant manner.
There are various characterizations of the algorithm, which link it to other areas in theoretical computer science (see also Further Related Work). For example, recent results in the context of machine learning show that 1-WL is as expressive as graph neural networks with respect to distinguishing graphs [37]. Following Grohe [17], an indicator to investigate the expressive power of the algorithm is the so-called WL dimension of a graph, defined as the minimal dimension of the WL algorithm required in order to distinguish the graph from every other non-isomorphic graph.
There is no fixed dimension of the algorithm that decides graph isomorphism in general, as was proved by Cai, Fürer, and Immerman [10]. Still, when focusing on particular graph classes, often a bounded dimension of the algorithm suffices to identify every graph in the class. This proves that for the considered class, graph isomorphism is solvable in polynomial time, since k-WL can be implemented to run in time O(n k+1 log n) [28]. For example, it the general question is still open. Our results imply that every connected constituent graph of an association scheme is either a cycle or 3-connected. Such a statement was previously only known for symmetric association schemes [33], which are far more restricted than the general ones.
A natural use case of these results is to determine or to improve upper bounds on the WL dimension of certain graph classes. As a first application in this direction, we obtain a new upper bound of k on the WL dimension for graphs of treewidth at most k. Based on [12], we also provide a new lower bound for this graph class, thus delimiting the value of the WL dimension of the class of graphs of treewidth bounded by k to the interval ⌈ k 2 ⌉ − 2, k .
Further Related Work Apart from its correspondence to counting logics, the WL algorithm has surprising links to other areas. For example, the algorithm has a close connection to Sherali-Adams relaxations of particular linear programs [3,21] and captures the same information as certain homomorphism counts [13]. It can also be characterized via winning strategies in so-called pebble games [22], which are a particular family of Ehrenfeucht-Fraissë games. The survey column [30] discusses the results of this article in the context of a general treatment of the WL algorithm and its dimension. As mentioned above, 1-WL essentially corresponds to graph neural networks. In order to make them more powerful, the authors of [37] propose an extension of graph neural networks based on k-WL (see also [36]).
Towards understanding the expressive power of the algorithm, in a related direction of research, it has been studied which graph properties the WL algorithm can detect, which may become particularly relevant in the graph-learning framework. In this context, Fürer [15] as well as Arvind et al. [2] have obtained results concerning the ability of the algorithm to detect and count certain subgraphs.

Graphs
A graph is a pair G = V (G), E(G) of a vertex set V (G) and an edge set E(G) ⊆ {u, v} u, v ∈ V (G) . Unless explicitly stated otherwise, every graph considered in this paper is finite, undirected, and simple (i.e., it contains no loops or multiple edges). For v, w ∈ V (G), we also write vw as a shorthand for {v, w}. The neighborhood of v is denoted by N (v), and the closed neighborhood of v is N [v] := N (v) ∪ {v}. The degree of v, denoted by deg(v), is the number of edges incident with v. For A ⊆ V (G) we define N (A) := v∈A N (v) \ A. A walk of length k from v to w is a sequence of vertices v = u 0 , u 1 , . . . , u k = w such that u i−1 u i ∈ E(G) for all i ∈ {1, . . . , k}. A path of length k from v to w is a walk of length k from v to w for which all occurring vertices are pairwise distinct. We refer to the distance between two vertices v, w ∈ V (G) by dist (v, w). For a set A ⊆ V (G), we denote by G [A] the induced subgraph of G on vertex set A. Also, we denote by G − A the subgraph induced by the complement of A, that is, the graph G − A := G[V (G) \ A]. A set S ⊆ V (G) is a separator of G if G − S has more connected components than G. A k-separator of G is a separator of G of size k. A vertex v ∈ V (G) is a cut vertex if {v} is a separator of G. The graph G is k-connected if it is connected and has no separator of size at most k − 1.
An isomorphism from G to another graph H is a bijection φ : V (G) → V (H) that respects the edge relation, that is, for all v, w ∈ V (G), it holds that vw ∈ E(G) if and only if a r X i v φ(v)φ(w) ∈ E(H). Two graphs G and H are isomorphic (G ∼ = H) if there is an isomorphism from G to H. We write φ : G ∼ = H to denote that φ is an isomorphism from G to H.
A vertex-colored graph is a tuple (G, λ), where G is a graph and λ : V (G) → C is a mapping into some set C of colors. Similarly, an arc-colored graph is a tuple (G, λ), where G is a graph and λ : v} ∈ E(G)} → C is a mapping into some color set C. Typically, C is chosen to be an initial segment [n] := {1, . . . , n} of the natural numbers. Isomorphisms between vertex-and arc-colored graphs have to respect the colors of the vertices and arcs. Usually, we will not distinguish between a colored graph (G, λ) and its uncolored version G, and also use G to denote the colored graph (G, λ).
We recall the definition of the treewidth of a graph. For more background on tree decompositions and treewidth, we refer the reader to [32]. Let G be a graph. A tree decomposition of G is a pair (T, β) where T is a tree and β : V (T ) → 2 V (G) is a function (where 2 V (G) denotes the power set of V (G)) such that 1. for every v ∈ V (G), the set {t ∈ V (T ) | v ∈ β(t)} is non-empty and induces a connected subgraph in T , and 2. for every e ∈ E(G), there is a t ∈ V (T ) such that e ⊆ β(t).
The sets β(t) for t ∈ V (T ) are the bags of the tree decomposition. The width of a tree decomposition (T, β) is The treewidth of G, denoted by tw(G), is the minimum width of a tree decomposition of G.

The Weisfeiler-Leman Algorithm
Let χ, χ ′ : V k → C be colorings of the k-tuples of vertices of G, where C is some finite set of colors. We say χ ′ refines χ if for allv,w ∈ V k , we have that χ ′ (v) = χ ′ (w) implies χ(v) = χ(w). The k-dimensional WL algorithm is a procedure that, given a graph G and a coloring χ of its k-tuples of vertices, computes an isomorphism-invariant coloring that refines χ. (Here, isomorphism invariance means that every isomorphism from the graph to a second graph preserves the colors of vertex k-tuples in the computed colorings on the graphs. ) We describe the mechanisms of the algorithm in the following. For an integer k > 1 and a vertex-colored graph (G, λ), we let χ 0 G,k : V k → C be the coloring where each k-tuple is colored with the isomorphism type of its underlying ordered colored subgraph. More formally, χ 0 G,k (v 1 , . . . , v k ) = χ 0 G,k (w 1 , . . . , w k ) if and only if for all i ∈ [k], it holds that λ(v i ) = λ(w i ) and for all i, j ∈ [k], it holds that v i = v j ⇔ w i = w j and v i v j ∈ E(G) ⇔ w i w j ∈ E(G). If G is arc-colored, the arc colors must be respected accordingly.
We then recursively define the coloring χ i G,k obtained after i rounds of the algorithm. Let χ i+1 G,k (v 1 , . . . , v k ) := (χ i G,k (v 1 , . . . , v k ); M), where M is a multiset defined as the partition of the vertex k-tuples induced by χ i+1 G,k is not strictly finer than the one induced by χ i G,k . For this value of i, we call the coloring χ i G,k the final coloring of G and denote it by χ G,k . If G is clear from the context or irrelevant, we also use the notation χ k for χ G,k .
The original WL algorithm is its 2-dimensional variant [41]. Since that version is the central algorithm of this paper, we omit the index 2 and write χ G instead of χ G,2 .
For each k ∈ N, the k-dimensional WL algorithm (k-WL) takes as input a (vertex-or arc-)colored graph (G, λ) and returns the final coloring χ G,k .
For two graphs G and H, we say that k-WL distinguishes G and H if there is a color c such that the sets {v |v ∈ V (G) k , χ G,k (v) = c} and {w |w ∈ V (H) k , χ H,k (w) = c} have different cardinalities. We write G ≃ k H if k-WL does not distinguish G and H. The algorithm identifies G if it distinguishes G from every non-isomorphic graph H. We also regularly exploit the fact that k-WL can detect certain graph properties. Let f G : (V (G)) ℓ → S be a function defined on ℓ-tuples of vertices for a graph G (for example, f G might be the distance function for pairs of vertices). For k ≥ ℓ, we say that k-WL knows f G if the implication holds for all graphs G, H and vertices v 1 , . . . , v ℓ ∈ V (G) and w 1 , . . . , w ℓ ∈ V (H). For a property P G ⊆ (V (G)) ℓ , we say that k-WL knows P G (in G) if k-WL knows the characteristic function of P G . For example, the statement that k-WL knows whether two vertices are at distance d from each other and that k-WL knows the set of pairs of vertices of distance d from each other can be used equivalently.

Finally, if V (H) ⊆ V (G), we say that k-WL knows H (in G) if k-WL knows V (H) and E(H).
Pebble Games For further analysis, it is often cumbersome to work with the WL algorithm directly and more convenient to use the following characterization via pebble games, which is known to capture the same information. Let k ∈ N. For graphs G and H on the same number of vertices and with vertex colorings λ G and λ H , respectively, we define the bijective k-pebble game BP k (G, H) as follows: The game has two players called Spoiler and Duplicator. The game proceeds in rounds, each of which is associated with a pair of positions The initial position of the game is a pair of vertex tuples of equal length ℓ with 0 ≤ ℓ ≤ k.
If not specified otherwise, the initial position is the pair (), () of empty tuples. Each round consists of the following steps. Suppose the current position of the game is (v,w) = ((v 1 , . . . , v ℓ ), (w 1 , . . . , w ℓ )). First, Spoiler chooses whether to remove a pair of pebbles or to play a new pair of pebbles. The first option is only possible if ℓ > 0, and the latter option is only possible if ℓ < k. If Spoiler wishes to remove a pair of pebbles, he picks some i ∈ [ℓ] and the game moves If there is no position of the play such that Spoiler wins, then Duplicator wins.
We say that Spoiler (and Duplicator, respectively) wins BP k (G, H) if Spoiler (and Duplicator, respectively) has a winning strategy for the game. Also, for a position (v,w) withv ∈ V (G) ℓ andw ∈ V (H) ℓ , we say that Spoiler (and Duplicator, respectively) wins BP k (G, H) from position (v,w) if Spoiler (and Duplicator, respectively) has a winning strategy for the game started at position (v,w). The next theorem describes the correspondence between the WL algorithm and the introduced pebble games. 1 ▶ Theorem 2.1 (see, e.g., [10,17]). Let k ≥ 1. Let G and H be two graphs and Association Schemes Let V be a set. An association scheme on V is an ordered partition An association scheme is symmetric if With each R i , we associate a constituent graph G(R i ) of the association scheme, defined as G(R i ) := (V, R i ∪ R ⊺ i ). Note that, formally, G(R i ) is directed because its edges are ordered pairs. However, since for every pair of vertices v, w ∈ V , it holds that (v, w) ∈ E(G(R i )) if and only if (w, v) ∈ E(G(R i )), we may also consider G(R i ) as undirected, i.e., E(G(R i )) as a set of unordered pairs of vertices.
Every association scheme induces a coloring on V 2 , in which every (v, w) is colored with the relation it is contained in. This coloring is stable with respect to 2-WL, which means that it is not refined by 2-WL (when V is interpreted as the vertex set of a complete directed graph). In particular, for all i ∈ [d] and all v, w ∈ V , it holds that induces an association scheme in which the relations R i are the color classes of the coloring χ G = χ G,2 .

One Color
Our first goal is to prove that 2-WL distinguishes vertex pairs that are separators in a graph from other pairs of vertices. This result forms the central technical contribution of this paper. We first sketch the proof strategy. Consider two graphs G and H and vertices v 1 , v 2 ∈ V (G) and w 1 , As it turns out (and as we show in detail in Section 5), the structural analysis of a graph with an arbitrary number of χ 2 -colors reduces to the case that there are at most two χ 2 -colors present in the graph. The crucial observation for the reduction is that one can bypass all vertices whose χ 2 -color is not contained in {c 1 , c 2 }. Here, bypassing a vertex u means removing u from the graph and connecting every pair of its neighbors via an edge.
Hence, we first focus on input graphs G for which In this section, we start with an analysis of the graphs in which all vertices are assigned the same color by 2-WL. In particular, this includes all constituent graphs of association schemes. In the next section, we will extend the techniques to graphs G for which |{χ G (w, w) | w ∈ V (G)}| = 2 holds. Finally, the reduction to two vertex colors is presented in Section 5.
So, for now, suppose that all vertices of the input graph are assigned the same color by 2-WL. A main tool for the analysis are distance patterns of vertices. For a graph G and a , since 2-WL knows the distance function for pairs of vertices (see, e.g., [11,Theorem 2.6.7]).
Suppose the statement is false and let d ∈ N be the maximal number such that d has distinct multiplicities in the two multisets. Let m 1 be the multiplicity of d in the first multiset and m 2 be the multiplicity of d in the second. Without loss of generality, assume that m 1 > m 2 . Then where the first equality is trivial and the second equality follows from the maximality of d. However, then D(u) and D(v) contain the number d + 1 in distinct multiplicities, a contradiction. ◀ a r X i v Throughout the remainder of this section, if not explicitly stated otherwise, we make the following assumption.
▶ Assumption 3.2. G is a connected graph on n vertices with the following properties: In the rest of this section, we analyze the structure of G and ultimately prove that G must be a cycle. In particular, this completely characterizes constituent graphs of association schemes that are connected, but not 3-connected.
Before diving into the technical details, we again give some intuition. Let d := dist(w 1 , w 2 ) and let C be a connected component of G − {w 1 , w 2 } such that |C| ≤ n−2 2 . We first argue that dist(v, w i ) ≤ d for all v ∈ C and i ∈ {1, 2} by analyzing distance patterns of vertices. Intuitively speaking, if v is far away from both w 1 and w 2 , then more than half of the vertices of G (specifically, all vertices in V (G) \ C) are closer to w 1 and w 2 than to v, which eventually contradicts the fact that all distance patterns are identical.
Then, we split the vertices into subclasses C i,j := {v ∈ C | dist(v, w 1 ) = i, dist(v, w 2 ) = j} for i, j ≤ d and analyze the connections between those sets. To this end, we may assume that the edge set of the input graph is maximal (among all graphs satisfying Assumption 3.2). To see how we can exploit this property, consider the simple example of four vertices , the vertices form a 4-cycle) and d ≥ 3. Also consider a pair u 1 , u 3 In particular, since d ≥ 3, we know that u 1 and u 3 are either both contained in C ∪ {w 1 , w 2 } or they are both not contained in C. Hence, by inserting all edges u 1 u 3 for which χ G (v 1 , v 3 ) = χ G (u 1 , u 3 ) holds into the graph, we preserve Condition 2 from Assumption 3.2. Also, χ G remains a stable coloring of the updated graph, which implies that Condition 1 from Assumption 3.2 is preserved. As a result, we may assume that all cycles on four vertices induce a clique which, in particular, implies that every pair of vertices is connected by at most one shortest path of length 2.
By extending this argument to cycles of length strictly less than 2d, we obtain that shortest paths of length strictly less than d are unique. This provides us with strong restrictions on the connections between the sets C i,j . Ultimately, this allows us to prove that G is a cycle by showing the existence of a vertex of degree 2. Note that Condition 1 of Assumption 3.2 implies that G is regular, i.e., deg(u) = deg(v) for all u, v ∈ V (G). This is a consequence of Condition 1 in Assumption 3.2, since 2-WL distinguishes cut vertices from other vertices (see [31,Corollary 7]) and there is no graph in which every vertex is a cut vertex. To see this, note that in the unique block-cut tree decomposition of the graph into its 2-connected components (see, e.g., [40]), each leaf component contains a vertex that is not a cut vertex.
The lemma implies that each of w 1 and w 2 has at least one neighbor in each of the connected components of G − {w 1 , w 2 }. ▶ Lemma 3.4. Let C be the vertex set of a connected component of G − {w 1 , w 2 } such that |C| < n 2 and let v ∈ C. Then there is no vertex u ∈ N (v) such that dist(u, w 1 ) < dist(v, w 1 ) and dist(u, w 2 ) < dist(v, w 2 ).

Proof. Suppose towards a contradiction that such a vertex
This is a contradiction. ◀ ▶ Lemma 3.5. Let d := dist(w 1 , w 2 ) and let C be the vertex set of a connected component Proof. By symmetry, it suffices to prove dist(v, w 2 ) ≤ d. The statement is proved by induction on ℓ := dist(v, w 1 ). For ℓ = 0, it holds that v = w 1 and dist(w 1 , w 2 ) = d. So suppose the statement holds for all u ∈ C ∪ {w 1 , Proof. Suppose towards a contradiction that w 1 w 2 ∈ E(G). Let C be the vertex set of a connected component of G − {w 1 , w 2 } such that |C| ≤ n−2 2 . By Lemma 3.5, we conclude that C ⊆ N (w 1 ) ∩ N (w 2 ). Let v ∈ C. Since G is 2-connected, the vertex w 1 must have at least one neighbor in V (G) \ C, in addition to being adjacent to all vertices in C and to w 2 . Thus, deg( Proof. By Lemma 3.6, it holds that w 1 w 2 / ∈ E(G). Furthermore, by the assumption of the lemma, we have dist(w 1 , w 2 ) = 2. Let C be the vertex set of a connected component of By Lemma 3.5, we conclude that C i,j = ∅ unless (i, j) ∈ {(1, 1), (1, 2), (2, 1), (2, 2)}. Suppose there exists v ∈ C 1,2 . We have D(v) = D(w 1 ) and, by Lemma 3.3, also N (w 1 ) ∩ C ′ ̸ = ∅. Thus, there is a vertex u ′ ̸ = w 1 such that dist(w 1 , u ′ ) < dist(v, u ′ ) and therefore, by Lemma 3.1, there is also a vertex u ̸ = v such that dist(v, u) < dist(w 1 , u). Note that u = w 2 is not possible since dist(v, w 2 ) = 2 = dist(w 1 , w 2 ). Suppose u ∈ C ′ . Then no shortest path from v to u uses w 1 , but this implies that dist(v, u) = 2 + dist(w 2 , u) = dist(w 1 , w 2 ) + dist(w 2 , u) ≥ dist(w 1 , u), a contradiction. Hence, u ∈ C, which implies that dist(w 1 , u) ≤ 2. So dist(v, u) = 1, meaning that u ∈ N (v). Therefore, by Lemma 3.1, for . Because w 2 is not a cut vertex (cf. Lemma 3.3), from every v ′ ∈ C ′ , there is a path to w 1 that does not contain w 2 . However, this is only possible if there is no vertex v ′ ∈ C ′ such that dist(w 1 , v ′ ) > 1. In other words, The combination of both inequalities yields |C ′ | + 1 ≤ |C|, which implies n = 2 + |C| + |C ′ | ≤ 1 + 2|C| ≤ n − 1, a contradiction. So C 1,2 = ∅ and, by symmetry, it also holds that C 2,1 = ∅. But then C 2,2 = ∅ by Lemma 3.4.

a r X i v
So C = C 1,1 , which means that C ⊆ N (w 1 ) ∩ N (w 2 ). In particular, deg( ] contains only one non-edge. Now by Condition 1 in Assumption 3.2, this also has to hold for w 1 , and hence, since no vertex in C ∩ N (w 1 ) is adjacent to any vertex in C ′ ∩ N (w 1 ), it must hold that deg(w 1 ) = 2. Therefore, by regularity, all vertices in G have degree 2 and thus, being connected, G is a cycle. ◀ We are now ready to show that G is a cycle.
▶ Lemma 3.8. G is a cycle.
Proof. Note that every graph that satisfies Assumption 3.2 has at least n edges because the graph must be regular and connected. We first argue that it suffices to prove the lemma for the case that G is a graph with a maximum edge set that satisfies Assumption 3.2. Indeed, if it holds for such a graph G, then G has n edges, so every graph that satisfies Assumption 3.2 with an edge set that is not maximal with respect to inclusion would have to have less than n edges. However, there are no such graphs. So in the following, we assume that the edge set of G is maximal with respect to inclusion. Let d := dist(w 1 , w 2 ). By Lemmas 3.6 and 3.7, we can assume that d ≥ 3. Let C be the vertex set of a connected component of This situation is also visualized in Figure 3.1.
In the following, the strategy is to prove that C i,j = ∅ whenever i + j > d. We first show that there cannot be any vertex in C of distance at least d − 1 both to w 1 and w 2 (see Claim 3.9). For the remaining sets C i,j , we exploit the edge maximality of G to reduce the complexity of vertex connections in C (see Claims 3.10 and 3.11). For example, we argue that shortest paths between vertices of distance strictly less than d are unique. This severely restricts possible connections between the sets C i,j and eventually allows us to argue that we can assume C i,j = ∅ whenever i + j > d (using Claims 3.12 and 3.13). Finally, we argue that |C i,j | = 1 whenever i + j = d, again relying on the fact that certain shortest paths are unique (see the application of Claim 3.14).
Suppose, for the sake of a contradiction, that In the base case i = ℓ, the statement holds by definition.
Now let v ′ ∈ C 1,d and consider an arbitrary vertex u ̸ = v ′ such that dist(v ′ , u) < dist(w 1 , u). Then u ∈ C and dist(v ′ , u) ≤ d − 1 by Lemma 3.5. Since D(v ′ ) = D(w 1 ), we conclude that for every vertex u ̸ = w 1 with dist(v ′ , u) > dist(w 1 , u), it holds that dist(w 1 , u) ≤ d−1 (cf. Lemma 3.1). Hence, there is no vertex u ∈ C ′ such that dist(w 1 , u) = d. Indeed, every such vertex would have to satisfy dist(w 1 , u) ≥ dist(v ′ , u), i.e., every shortest path from u to v ′ would have to pass through w 2 . However, since dist(v ′ , w 2 ) = d, such a path has length at least d + 1. Since there is no cut vertex in G, this excludes also the existence of vertices u ∈ C ′ such that dist(w 1 , u) > d. Hence, we obtain that dist(w 1 , u) ≤ d − 1 holds for every u ∈ C ′ .
Overall, this means that, on the one hand, dist( Then there is a unique shortest path from u to v. Proof. Suppose the statement does not hold and let ℓ < d be the minimal number for which the claim is violated. Let u, v ∈ V (G) be two vertices with dist(u, v) = ℓ such that there are two paths of length ℓ from u to v. Also let i.e., the graph obtained from G by inserting all (undirected) edges contained in the set E ′ . We argue that G ′ still satisfies Assumption 3.2, which contradicts the edge maximality of G. First, the coloring χ G is also a stable coloring of G ′ , which implies that χ G refines the coloring χ G ′ . In particular, Condition 1 of Assumption 3.2 is satisfied for the graph G ′ . Now let u ′ v ′ ∈ E ′ . Then dist(u ′ , v ′ ) = ℓ and there are at least two different walks of length ℓ from u ′ to v ′ because the same statement holds for u and v. Due to the minimality of ℓ, the two walks are internally vertex-disjoint paths. If u ′ and v ′ lie in different connected components of G − {w 1 , w 2 }, then one of the two paths must pass through w 1 while the other one passes through w 2 , forming a cycle of length 2ℓ < 2d. This implies dist(w 1 , w 2 ) < d, a contradiction. Thus, we conclude that there is a connected component with vertex set C of Proof. Suppose the statement does not hold and let ℓ < d be the minimal number for which the claim is violated.
Similarly to the previous claim, we argue that G ′ still satisfies Assumption 3.2, which contradicts the edge maximality of G.
Indeed, by the same argument as in the previous claim, Condition 1 of Assumption 3.2 is satisfied for the graph G ′ .
Note that 2-WL knows whether such a walk exists, since the shortest path is unique by Claim 3.10 and the algorithm knows the number of triangles that share an edge with the shortest path. Due to the minimality of ℓ, it holds that the unique shortest path from (using the same arguments as before). But this again means Condition 2 of Assumption 3.2 is also satisfied for G ′ . ◁ These claims drastically restrict the structure of the graph G and will allow us to prove that G is a cycle. Intuitively speaking, the claims imply that, for each of the w i , the graph induced by w i and all vertices in G[C] with distance at most d − 1 to w i is sufficiently similar to a tree.
Proof. This follows directly from Claim 3.10. ◁ Proof. Let i be as described in the claim and let v ∈ C i,k−i . By Claim 3.12 and the maximality of k, we obtain that Since via v and u ′ , there is a path from u to w 1 of length i + 1, we can apply Claim 3.11 to deduce that u ′ ∈ N (u). Indeed, by the definition of the C i,k−i , no other shortcuts on the path are possible. Swapping the roles of u and v, we obtain that u and v agree on their neighbors of distance i − 1 to w 1 . By applying the same argument also for paths from u and v to w 2 , we conclude that ] contains at most one non-edge, namely between the vertices in N (v) \ C i,k−i . So the same has to be true for w 1 , which implies that deg(w 1 ) = 2. ◁ Hence, we can assume that Let forms a clique, since there is a unique shortest path between pairs of vertices at distance 2 by Claim 3. 10 , since there is a unique shortest path between pairs of vertices at distance 2 by Claim 3.10. Finally, let forms a clique and thus, the same must hold for N [w 1 ], which is a contradiction, since w 1 belongs to a separator.
In the other case, is a matching graph (i.e., every vertex in the graph has degree 1) Proof. This follows directly from Claim 3.10. ◁ Since G is regular, we further conclude that for every i with By Claim 3.14 and the definition of the sets Since v ∈ C i,d−i was chosen arbitrarily, it follows that C i,d−i forms a clique. Now suppose that |C i,d−i | ≥ 2 holds for some (and therefore every) i with 1 ≤ i ≤ d − 1. Then G contains an induced subgraph isomorphic to C 4 , which contradicts Claim 3.10 (recall Reformulating the previous lemma, we obtain the following theorem. Then (exactly) one of the following holds: Note that the complete graphs on 2 and 3 vertices are 3-connected. The theorem also implies that a connected constituent graph of an association scheme is either 3-connected or a cycle. It thus provides a generalization of Kodalen's and Martin's result in [33], where they proved the theorem in case the graph stems from a symmetric association scheme. (For other work on the connectivity of relations in association schemes, see e.g. [7,8,9,14].)

Two Colors
Recall that our overall goal is to prove that 2-WL assigns special colors to 2-separators. We will use Lemma 3.8 to prove this in case the tuples (u, u) and (v, v) of a 2-separator {u, v} obtain the same χ 2 -color. To treat the much more difficult case that u and v obtain distinct colors, we intend to generalize the results of the previous section to two vertex colors. Maybe somewhat surprisingly, we obtain a statement that is similar to Lemma 3.8.
However, now we require the input graphs to be 2-connected instead of only being connected. This is a necessary condition, since, for example, the star graphs K 1,n for n ≥ 2 are neither 3-connected nor cycles but still, the image of χ 2 only contains two vertex colors for them. We shall prove the following theorem.
▶ Theorem 4.1. Let G be a 2-connected graph with the following properties: Then G is a cycle.
The route to proving the statement is similar to the one described in Section 3. Still, with two colors allowing for more complexity in the graph structure, the statements and proofs become more involved and additional cases need to be considered. To be more precise, using an induction on the order of G and additional insights and tools regarding 2-WL, the first step of the proof is to reduce the general case to one in which the partition into the two vertex color classes forms a bipartition of the graph (i.e., there are no edges between vertices of the same color). Let {U, V } be the partition of V (G) according to vertex colors. To achieve the reduction, we contract the connected components of G[U ] and G[V ] to single vertices. Here, we crucially exploit the fact that 2-WL "has access" to the factor graph and that thus, the factor graph still meets the requirements of the theorem.
To treat the case that {U, V } forms a bipartition, the strategy is essentially the same as in the previous section. We start by adapting several of the auxiliary lemmas given in the previous section to the setting of two vertex colors.

▶ Lemma 4.2. Let G be a connected graph with n vertices and suppose {w
Proof. The proof is analogous to the one for Lemma 3.4. ◀ ▶ Lemma 4.3. Let G = (U, V, E) be a 2-connected bipartite graph with n vertices and the following properties: Let d := dist(w 1 , w 2 ) and let C be the vertex set of a connected component of Proof. Since G is bipartite, d is odd. By symmetry, it suffices to show the statement for i = 2. For u ∈ U ∩ C, we prove by induction on ℓ := dist(u, w 1 ) that dist(u, w 2 ) ≤ d. Then the statement follows, because every v ∈ V ∩ C is connected to some u ∈ U ∩ C.
by Lemma 4.2 and the induction hypothesis. But since G is bipartite and we know that u ′ ∈ U and w 2 ∈ V , we have that dist(u ′ , w 2 ) is odd and thus, dist be a 2-connected bipartite graph with n vertices and the following properties: Then Proof. Since G is bipartite and by symmetry, we only need to consider the case that w 1 ∈ U and w 2 ∈ V . Suppose towards a contradiction that We also require that 2-WL "has access" to certain factor graphs of G, which allows us to build an inductive argument in case G is not bipartite with a bipartition into the color classes. We present the necessary tools next.
Let G be a graph and let Moreover, let A 1 , . . . , A ℓ be the vertex sets of the connected components of G[C]. We define G/C to be the graph obtained from contracting every set A i to a single vertex. Formally, a r X i v ▶ Lemma 4.5 (see [11,Theorem 3.1.11]). Let G be a graph and Then χ G /C is a stable coloring of the graph G/C with respect to 2-WL.
Also, for all We can use the lemma to deduce the following corollary, which will turn out to be useful for the induction that we perform afterwards to prove Theorem 4.1.
▶ Corollary 4.6. Let G be a graph and suppose there are colors Then With this, we are now ready to prove the main result of this section.
Proof of Theorem 4.1. By Lemma 3.8, we can assume without loss of generality that . The statement is proved by induction on the graph order n. For n ≤ 4, a simple case analysis among the possible graphs G yields the statement.
So let n ≥ 5. Again, it suffices to prove the statement for the case that G is an n-vertex graph with a maximum edge set that satisfies the requirements of the theorem. Let Let U 1 , . . . , U k be the vertex sets of the connected components of G[U ] and let V 1 , . . . , V ℓ be the vertex sets of the connected components of G[V ]. Without loss of generality, assume that Proof. It is not hard to see that, by reasons of connectivity and since |U i | = |U j | and By symmetry, we may assume that there exists a vertex u 1 ∈ U 1 ∩ C with u 1 w 1 ∈ E(G). We first argue that U 1 ∩ C ′ = ∅. Towards a contradiction, suppose that there exists u ′ 1 ∈ U 1 ∩ C ′ . Then w 1 is a cut vertex in G[U 1 ]. Since 2-WL distinguishes arcs within connected components from arcs between different connected components, by [31,Corollary 7], all vertices in U 1 must be cut vertices, in addition to G[U 1 ] being connected. It is easy to see that there is no connected graph in which all vertices are cut vertices (see also the comment following Lemma 3.3). Analogously, we cannot have that both In this case, we have C ∪ {w 1 } = U 1 and, by regularity, uw 2 ∈ E(G) for all u ∈ U 1 . In particular, every vertex in U has exactly one neighbor in V . However, for w 1 , this neighbor must be distinct from w 2 because it must Note that for all j ̸ = 1 and all v ∈ V j , we have that However, for w 1 and any other vertex in U 1 , there is no equivalent vertex in V . Thus, w 1 is not incident to any edge of color χ G (u 1 , u 2 ). Hence, χ G (u 1 , u 1 ) ̸ = χ G (w 1 , w 1 ), which contradicts the assumptions. Therefore |U 1 | ≤ 2. Analogously, it can be shown that |V 1 | ≤ 2.
The case C ′ ⊆ U 1 ∪ V 1 follows by symmetry. Altogether, we deduce that G has to be a cycle. ◁ So for the rest of the proof, we assume that consist of at least two connected components each (again using the fact that G[U ] and G[V ] do not contain any cut vertices).
Let G ′ be the graph with V (G ′ ) = {U 1 , . . . , U k , V 1 , . . . , V ℓ } and whose edge sets consists of all U i V j for which there are u ∈ U i and v ∈ V j such that uv ∈ E(G). We argue that G ′ satisfies the requirements of the theorem. First note that Clearly, G ′ is connected because G is. So it remains to argue that G ′ is 2-connected. If not, then G ′ contains a cut vertex. Without loss of generality, assume that U i for a certain i ∈ [k] is a cut vertex. Then, since 2-WL recognizes cut vertices ( [31,Corollary 7]) and, by Corollary 4.6, every vertex U i with i ∈ [k] is a cut vertex of G ′ . Considering the cut tree of G ′ (i.e., the tree in which every cut vertex and every 2-connected component forms a vertex), it is not hard to see that this implies that every V j for j ∈ [ℓ] has only one neighbor. But this is only possible if C ⊆ V 1 or C ′ ⊆ V 1 , and we assumed the contraries of both cases.
Suppose that |V (G ′ )| < |V (G)|. Then, by the induction hypothesis, the graph G ′ is a cycle. Thus, every vertex in U is adjacent to vertices in exactly one or two connected components of G[V ].
We first consider the subcase that both C ∩ U 1 = ∅ and C ∩ V 1 = ∅ hold. The vertex w 1 is adjacent to vertices in a connected component with vertex set V j ⊆ C, whereas all vertices u ∈ U 1 with u ̸ = w 1 must be adjacent to the same connected component with vertex set V j ′ ⊆ (C ′ ∪ {w 2 }). In particular, we have j ̸ = j ′ . Assuming |U 1 | > 2, similarly as in the proof of Claim 4.7, we reach a contradiction considering χ G (w 1 , w 1 ). By symmetry, we cannot have |V 1 | > 2 either. The subcase that C ′ ∩ U 1 = ∅ and C ′ ∩ V 1 = ∅ can be treated analogously.
Thus, suppose without loss of generality that C ∩ U 1 ̸ = ∅ and C ′ ∩ V 1 ̸ = ∅. (The case that C ′ ∩ U 1 ̸ = ∅ and C ∩ V 1 ̸ = ∅ follows by symmetry.) Since we cannot have that C = U 1 \{w 1 }, there must be a connected component with vertex set V j ⊂ C for a certain j ̸ = 1 such that for every Again, we reach a contradiction when assuming that |U 1 | > 2 and, by symmetry, also for the assumption |V 1 | > 2.
Now assume |V (G ′ )| = |V (G)|. This means that G is a bipartite graph with bipartition {U, V } and all U i and all V j are singletons. From Lemma 4.4, we know that w 1 w 2 / ∈ E(G). Let d := dist(w 1 , w 2 ). Note that d is odd and thus, d ≥ 3.
Then there is a unique shortest path from u to v.
Proof. Suppose the statement does not hold and let ℓ < d be the minimal number for which the claim is violated. Let u, v ∈ V (G) be two vertices with dist(u, v) = ℓ such that there are two paths of length ℓ from u to v. Also, let . We argue that G ′ still satisfies the assumptions of the theorem, which contradicts the edge maximality of G.
First, the coloring χ G is also a stable coloring of G ′ , which implies that χ G refines the coloring χ G ′ . In particular, for every v ∈ V (G), there is an i ∈ {1, 2} such that Then dist(u ′ , v ′ ) = ℓ and there are at least two different walks of length ℓ from u ′ to v ′ , because the same statement holds for u and v. Due to the minimality of ℓ, the two walks are vertex-disjoint paths. If u ′ and v ′ lie in different connected components of G − {w 1 , w 2 }, then one of the two paths must pass through w 1 while the other one passes through w 2 , forming a cycle of length 2ℓ < 2d. This implies dist(w 1 , w 2 ) < d, a contradiction. Thus, we conclude that there is a connected component C of G − {w 1 , w 2 } such that u ′ , v ′ ∈ C ∪ {w 1 , w 2 }. But this means that {w 1 , w 2 } is also a 2-separator of the graph G ′ . ◁ Proof. We argue that deg(u) = 2 for every u ∈ U . Analogously, one can prove that deg(v) = 2 for every v ∈ V , which together means that G is a cycle.
there would be two shortest paths from u to w 1 or two shortest paths from u to w 2 , contradicting Claim 4.8. Now suppose towards a contradiction that deg(u) > 2. Then there There is an edge between two sets whenever there may be edges connecting vertices from the two sets. Thus, we can assume that C 2,3 = ∅. Hence, we have C i,d−i = ∅ for every 1 ≤ i ≤ 4 and therefore C 1,6 ̸ = ∅ and C i,7−i ̸ = ∅ for every 1 ≤ i ≤ 6. Analogously as in the proof of Claim 4.9, there are vertices u ∈ C 4,3 and v ∈ N (u) ∩ C 5,4 , supposing deg(u) > 2. We have N (v) ⊆ C 4,3 ∪ C 4,5 ∪ C 6,3 ∪ C 6,5 . By Claim 4.8, we have |N (v) ∩ (C 4,3 ∪ C 6,3 )| ≤ 1. We would like to apply the same argument to N (v) ∩ (C 4,3 ∪ C 4,5 ). However, since dist(v, w 1 ) = 5 = d, we cannot apply Claim 4.8 immediately. Still, note that every shortest path from w 1 to w 2 with all internal vertices in C has length 7. Therefore, analogously as in the proof of Claim 4.8, using the edge maximality of G, we can show that there cannot be cycles of length at most 10 in G and that, thus, there must be a unique shortest path from v to w 1 . In particular, this If w 2 has only one neighbor v in C ′ , then {w 1 , v} is a unicolored 2-separator. Consider the graph G with vertex set U and an edge between every pair of vertices u, v if there is a path from u to v of length 2 (i.e., via a vertex in V ) in G. Since 2-WL knows whether such paths exist, we can apply Theorem 3.15. It is easy to see that G is connected and not 3-connected. Thus, it must be a cycle. In particular, every vertex in G has degree 2. Therefore, the position of each vertex in V is uniquely determined: the graph G is a subdivision of G. Thus, G is a cycle. Now assume First suppose C 1,2 ̸ = ∅ and, equivalently, . Furthermore, by a similar reasoning, we have that |N (C 4,1 ) ∩ C 3,2 | = |C 4,1 | · (r U − 1). Every vertex in C 3,2 has distance 2 to w 2 and thus has a neighbor in C 2,1 ∪ C 4,1 . Note that N (w 2 ) ∩ C = C 2,1 ∪ C 4,1 . Now since, by Claim 4.8, we have Let v ∈ C 1,2 . Similarly as above, |N (v) ∩ C 2,3 | = r V − 2. Furthermore, for every vertex u ∈ N (v) ∩ C 2,3 , by Claim 4.8 and Lemma 4.2, we have that N (u) ⊆ C 1,2 ∪ C 3,2 and |N (u) ∩ C 1,2 | = 1. Again using Claim 4.8, every two vertices in N (v) ∩ C 2,3 must have disjoint neighborhoods in C 3,2 . Thus, we obtain that |C 3,2 | ≥ (r V − 2)(r U − 1).
Altogether, we obtain (r , which is a contradiction. This concludes the proof. ◁ The claim completes the proof of the theorem. ◀

Detecting Decompositions with Weisfeiler and Leman
In this section, we show that 2-WL implicitly computes the decomposition of a graph into its 3-connected components. As a main step, we first complete the proof that 2-WL distinguishes 2-separators from other pairs of vertices, building on the results from Sections 3 and 4. Afterwards, we derive several consequences of this result by falling back on ideas developed in [31]. Let S be a set of vertex colors. We say a path u 0 , . . . , u ℓ avoids S if χ G (u i , u i ) / ∈ S holds for all i ∈ [ℓ − 1]. Note that we impose no restriction on the colors of the endpoints of the path. It is easy to see that, given two vertices u, v ∈ V (G), the algorithm 2-WL knows if there is a path from u to v that avoids S.
We write G| S for the graph (V, Proof. Since 2-WL knows whether there is a path between two vertices that avoids S, there is a set of colors T such that uv ∈ E if and only if χ G (u, v) ∈ T . Hence, every refinement performed by 2-WL in G| S will also be done in G. ◀

▶ Theorem 5.2. Let G and H be two graphs such that
Proof. Since the multisets of colors that the 2-WL algorithm computes in two graphs are either equal or disjoint (see, e.g., [29,Lemma 3.4]), the assumptions of the theorem imply that 2-WL does not distinguish between G and H. Let S := {χ G (w 1 , w 1 ), χ G (w 2 , w 2 )} and let G ′ := G| S . Clearly, the graph G ′ is connected. We argue that G ′ is 2-connected. Suppose towards a contradiction that there is a cut vertex w in G ′ . Let C and C ′ be the vertex sets of two connected components of G ′ − {w}.
Let v ∈ C and v ′ ∈ C ′ . Suppose there is a path P from v to v ′ in G that does not pass w. Then there is a corresponding path P ′ in G ′ , which simply skips all inner vertices of P whose χ 2 -color is not contained in S. In particular, P ′ connects v and v ′ , but avoids w. This contradicts w being a cut vertex in G ′ . Hence, Now assume |V (G ′ )| ≥ 3 and suppose there is a vertex set C of a connected component of Let C ′ be the vertex set of a second connected component of G − {w 1 , w 2 } and let v ∈ C ′ . Then w 1 and w 2 are the only vertices with color in S that can be reached from v via a path that avoids S. Since u). Because 2-WL knows whether there is a path between two vertices that avoids S, it follows that v 1 and v 2 can be reached from u via a path that avoids S. Moreover, it follows that χ G (v, v) = χ H (u, u). Using again the fact that 2-WL knows whether there is a path between two vertices that avoids S, this implies that there are exactly two vertices with color in S that can be reached from u via a path that avoids S. Together, this means that v 1 and v 2 are the only vertices with color in S that can be reached from u via a path that avoids S.  1 , w 2 ), (v 1 , v 2 )). This strategy can be turned into a winning strategy in the game BP 3 (G, H) from position ((w 1 , w 2 ), (v 1 , v 2 )) by maintaining the property that all pebbles are placed on C G and C H . Indeed, if Duplicator chooses a bijection f : V (G) → V (H) such that f (C G ) ̸ = C H , then Spoiler can place pebbles on w ′ ∈ V (G) and v ′ ∈ V (H) such that w ′ ∈ C G and v ′ / ∈ C H (or the other way around). Also, without loss of generality, the current position is not empty, i.e., there are pebbles already placed on some w ∈ C G and v ∈ C H . But now this is not the case, then Spoiler wins the game BP 3 (G ′ , H ′ ) from the initial position (w k−1 , w k ), (v k−1 , v k ) , again by Theorem 2.1. However, such a winning strategy can easily be translated to a winning strategy for Spoiler in BP k+1 (G, H) from the initial position (w 1 , . . . , w k ), (v 1 , . . . , v k ) by never touching the k − 2 first pebbles. This is a contradiction.
If G ′ is not connected, the same must hold for H ′ since 2-WL knows whether a graph is connected. First, suppose there are vertex sets C G , C ′ G of two connected components of G ′ such that C G , C ′ G ⊈ {w k−1 , w k }. Then there are also vertex sets C H , C ′ H of distinct connected components of H ′ such that C H , C ′ H ⊈ {v k−1 , v k }. In particular, {v 1 , . . . , v k } forms a k-separator in H.
Otherwise, G ′ has exactly two connected components with vertex sets C G , C ′ G and |C G | = 1 and C G ⊆ {w k−1 , w k }. Without loss of generality, assume that C G = {w k−1 }. Then H ′ has exactly two connected components with vertex sets C H , C ′ H , one of which, say C H , equals {v k−1 }. Let G ′′ := G ′ − {w k−1 } and H ′′ := H ′ − {v k−1 }. Since w k−1 and v k−1 , respectively, is the only isolated vertex in G ′ and H ′ , respectively, it follows that χ G ′′ (w k , w k ) = χ H ′′ (v k , v k ). But now, w k is a cut vertex in G ′′ . By [31,Corollary 7], it holds that v k is a cut vertex in H ′′ . This means that {v 1 , . . . , v k } forms a k-separator in H.
In the last case, both G ′ and H ′ are connected and {w k−1 , w k } forms a 2-separator in the graph Following [31], we say that k-WL determines orbits on a graph class G if for all arccolored graphs (G, λ), (G ′ , λ ′ ) with G, G ′ ∈ G, and for all v ∈ V (G) and v ′ ∈ V (G ′ ), there exists an isomorphism from (G, λ) to (G ′ , λ ′ ) mapping v to v ′ if and only if it holds that Using the corollary, we can prove a strengthened version of [31,Theorem 13]. The theorem says that on every minor-closed graph class G, it holds that if 3-WL determines vertex orbits on all arc-colored 3-connected graphs in G, then 3-WL also distinguishes all pairs of non-isomorphic graphs in G. We show that the same statement actually holds already when replacing the occurrences of 3-WL with 2-WL (see Theorem 5.7). Roughly speaking, the main step is to argue that 2-WL implicitly computes the decomposition into triconnected components (in the sense of Tutte). We can then prove the above statement using standard dynamic-programming arguments to decide isomorphism in a bottom-up fashion along the decomposition into triconnected components.
We start by formally defining what it means for 2-WL to implicitly compute a decomposition. Let G be a graph and let (T, β) be a tree decomposition of G. For the remainder of this section, we restrict ourselves to rooted tree decompositions, i.e., one node r ∈ V (T ), the root of T , is designated and all edges are directed away from the root. Also, we assume that β(s) ̸ ⊇ β(t) holds for all (s, t) ∈ E(T ). For every v ∈ V (G), define t v ∈ V (T ) to be the unique node closest to the root such that v ∈ β(t v ). Note that, by the above assumption, for ▶ Definition 5.4. Let G be a graph and let (T, β) be a rooted tree decomposition of G. For k ≥ 2, we say that k-WL implicitly computes (T, β) if there are two sets C bags , C edges ⊆ {χ G,k (v, w, . . . , w) | v, w ∈ V (G)} of colors such that and For simplicity, we restrict ourselves to the case k = 2 in the following. We start with some basic observations. Let G be a graph and suppose 2-WL implicitly computes a rooted tree decomposition (T, β) of G. Then there is also a set of colors Hence, each connected component of the graph G[C eq ] (recall the definition in the paragraph before Lemma 4.5) corresponds to one bag of the tree decomposition (T, β). Moreover, the rooted tree T can be reconstructed by considering the graph with vertex set V (G/C eq ) and edge set In particular, the rooted tree decomposition (T, β) can be reconstructed from the sets C bags and C edges . ▶ Definition 5.5. Let G be a graph class. The WL dimension of G, denoted by dim WL (G), is the minimum k ∈ N such that k-WL identifies every graph G ∈ G. (If there is no such k, set dim WL (G) to be ∞.) Intuitively speaking, arguing that 2-WL implicitly computes a certain type of tree decomposition can be a powerful tool for showing that the WL dimension of a graph class is bounded. It essentially suffices to show that k-WL can handle the graphs that are induced by the bags.
As an important example, we now argue that 2-WL implicitly computes the decomposition into triconnected components and thereby reduce the task of determining dim WL (G) of a minor-closed graph class G to dealing with all 3-connected graphs in G. Recall that, by our definition, all graphs of order at most 2 are 3-connected. The decomposition described in the theorem is the decomposition of a graph into triconnected components in the sense of Tutte. Hence, the only challenge is to prove that 2-WL implicitly computes this decomposition. The proof of the theorem uses the same arguments as the one for [31,Theorem 13] and it can be found in the appendix.
Building on a bottom-up dynamic-programming strategy along the decomposition into triconnected components, we can strengthen Theorem 13 from [31].
▶ Theorem 5.7. Let G be a minor-closed graph class and assume k ≥ 2. Suppose the k-dimensional WL algorithm determines orbits on the class of all arc-colored 3-connected graphs in G. Then the k-dimensional WL algorithm distinguishes all non-isomorphic graphs in G.
Again, the proof of the theorem follows the lines of the proof of [31,Theorem 13], exploiting the improved bound on the dimension of the WL algorithm required to distinguish 2-separators from other pairs of vertices stated in Theorem 5.2. For the sake of completeness, all details can be found in the appendix.
In [31], it was shown that the WL dimension of the class of planar graphs is either 2 or 3. As an application of Theorem 5.7, we obtain that the precise value only depends on the dimension needed to determine orbits on the class of all arc-colored 3-connected planar graphs.
As another consequence of our results, we show that 2-WL also knows sizes of connected components after removing a 2-separator. This particular result forms the basis for improving the upper bound on a parametrization of the WL dimension by the treewidth of the input graph in Section 6.
For a graph G and v 1

Proof. The statement trivially holds if
If {v 1 , v 2 } is not a 2-separator, the statement follows easily from Theorem 5.2. Thus, we may assume that {v 1 , v 2 } and {w 1 , w 2 } are 2-separators. Recall the notation G| S (preceding is the number of vertices that are reachable from v 3 without ever visiting a vertex with a color from S. This is encoded in the color χ G (v 3 , v 3 ). Since then v 1 and v 2 are the only vertices in V (G ′ ) that v 3 can reach via paths that avoid S. Also, as before, s G (v 1 , v 2 , v 3 ) is the number of vertices that are reachable from v 3 without ever visiting a vertex with a color in S. The same has to hold for w 1 and w 2 with respect to w 3 , since where C ′ ranges over all vertex sets of connected components of G − {v 1 , v 2 }. As discussed above, the sizes of these sets C ′ are encoded in the vertex colors of the graph G and the same is true for H.
Otherwise, {v 1 , v 2 } forms a 2-separator in G ′ and hence, G ′ is a cycle by Lemma 5.1 and Theorem 4.1. Note that |V (G ′ )| ≥ 4 and v 1 v 2 / ∈ E(G ′ ). Using Lemma 5.1, it follows that H| S is also a cycle. Also, |V (H| S )| ≥ 4 and w 1 w 2 / ∈ E(H| S ). Note that every vertex can reach only two vertices in S via paths that avoid S. Thus, the colors χ G (v, v ′ ) for vv ′ ∈ E(G ′ ) encode the number of vertices with color not in S for which v and v ′ are the only vertices reachable via paths that avoid S. Moreover, 2-WL knows the arc-colored cycle G ′ (and the analogous arc-colored cycle H ′ for H). Thus, it suffices to consider these two cycles, for which the statement is easy to see. ◀ The last theorem can also be formulated in terms of the expressive power of the 3-variable fragment C 3 of first-order logic with counting quantifiers of the form ∃ ≥k xφ(x). Indeed, it implies that for all n, s ∈ N, there is a formula φ n,s (x 1 , x 2 , x 3 ) ∈ C 3 such that, for every 2-connected n-vertex graph G and v 1 for details about the connection between the WL algorithm and counting logics, see, e.g., [10,17,28]).

New Bounds for Graphs of Treewidth k
As an application of the results presented so far, we investigate the WL dimension of the class of graphs of treewidth at most k. Up to this point, the best known upper bound on the WL dimension of such graphs has been k + 2, i.e., (k + 2)-WL identifies every graph of treewidth at most k [19]. In this section, we present new upper and lower bounds, as stated in the following theorem.
▶ Theorem 6.1. Let k ≥ 2. Then k 2 − 2 ≤ dim WL (T k ) ≤ k, where T k denotes the class of graphs of treewidth at most k.
Roughly speaking, for the upper bound, given two graphs G and H where G has treewidth at most k, we use the correspondence from Corollary 2.2 and force the players in the game BP k (G, H) to descend along a tree decomposition of width k in G. For this, we build on an extension of Theorem 5.8 to arbitrary separator sizes.
Meanwhile, the lower bound in Theorem 6.1 is an independent insight, i.e., it does not build on the results from the previous sections. Here, we define a family of difficult instances by applying a construction introduced by Cai, Fürer, and Immerman [10] to modified grid graphs.

Upper Bound
As indicated, the basic idea for proving a new upper bound is to provide a winning strategy for Spoiler in the corresponding bijective pebble game and it works similarly to the proof that (k + 2)-WL identifies every graph of treewidth at most k given in [19]. The main difference is a much more careful implementation of the general strategy in order to get by with the desired number of pebbles. As a major ingredient, we exploit that separators can be detected using fewer pebbles.
For a (k + 1)-tuple (v 1 , . . . , v k+1 ) of vertices of a graph G, we define where C is the vertex set of the unique connected component of ▶ Lemma 6.2. Suppose k ≥ 2. Let G and H be two graphs and consider two tuples . . . , w k+1 ). Then Spoiler wins the game BP k+1 (G, H) from the initial position Proof. It is easy to see that it suffices to prove the statement for the case that the following conditions hold: v k+1 / ∈ {v 1 , . . . , v k } and w k+1 / ∈ {w 1 , . . . , w k }, and G and H are connected and of the same order. Also note that, by Corollary 5.3, the graph G is 2-connected if and only if H is 2-connected.
First suppose k = 2. Assume the graphs are connected, but not 2-connected. We are going to use the correspondence from Theorem 2.1. The proof basically exploits the fact that the decomposition into 2-connected components has a tree-like structure and that 2-WL recognizes cut vertices (see [31,Corollary 7]), thus being able to "transport information" from one side of a cut vertex to the other. Note that v i is a cut vertex if and only if w i is a cut vertex.
First, suppose that exactly one vertex in {v 1 , v 2 } is a cut vertex, say v 1 . Then we can ignore the vertex v 2 . Also, for every v ′ ∈ V (G), the color triple formed by Otherwise, neither v 1 nor v 2 is a cut vertex. The only problematic case is that {v 1 , v 2 } forms a 2-separator (implying that v 1 and v 2 lie in a common 2-connected component of G). In this case, we can proceed analogously as in the proof of Theorem 5.8.
For the general case, i.e., k > 2, let G : −1 , w k , w k+1 ) and hence, Spoiler wins the game BP 3 ( G, H) from the initial position (v k−1 , v k , v k+1 ), (w k−1 , w k , w k+1 ) by Theorem 2.1 and the first part of the proof. But then Spoiler also wins the game BP k+1 (G, H) from the initial position (v 1 , . . . , v k+1 ), (w 1 , . . . , w k+1 ) by simply never moving the first k − 2 pebbles. ◀ To build Spoiler's strategy along a given tree decomposition, we use the following characterization of treewidth. Let G be a graph of treewidth k. For a k-separator S ⊆ V (G) and the vertex set C of a connected component of G − S, we define G(S, C) to be the graph on vertex set S ∪ C obtained by inserting a clique between the vertices in S into G[S ∪ C]. An ordered separator is a tupleā = (a 1 , . . . , a k ) where the underlying set {a 1 , . . . , a k } is a separator. In this proof, slightly abusing notation, we do not distinguish between ordered separators and their underlying unordered separators. For two ordered separators  H(b, m). Now let C ∈ C G (ā, m) be such that Also let Then there exist a v ∈ D and C G ∈ C G (ā, m) and C H ∈ C H (b, m) with v ∈ C G and f (v) ∈ C H and
Proof. To prove the claim, it suffices to argue that |A| > |B| where From the definitions of the number m and the set A, it follows that (G ′ ,ā, v) ∼ = (H ′ ,b, w). Now let A ′ ∈ A ′′ and let C be the vertex set of a connected component of (H ′ ,b, w). Overall, this proves the claim. ◁ Since m ′ < m, Spoiler wins from the initial position (ā ′ ,b ′ ) by the induction hypothesis. Using the induction principle, this completes the proof. ◀

Lower Bound
For the lower bound, we use a construction introduced by Cai, Fürer, and Immerman [10] and start by reviewing it. For a non-empty finite set S, we define the CFI gadget X S to be the following graph. For each w ∈ S, there are vertices a(w) and b(w), and for every A ⊆ S such that |A| is even, there is a vertex m A . For every A ⊆ S such that |A| is even, there are edges {a(w), m A } ∈ E(X S ) for all w ∈ A and {b(w), m A } ∈ E(X S ) for all w ∈ S \ A.
As an example, the graph X 3 := X [3] is depicted in Figure 6.1. The graph is colored so that {m A | A ⊆ S and |A| is even} forms a color class and so that {a(w), b(w)} forms a color class for each w ∈ S. Let G be a connected graph of minimum degree 2. For T ⊆ E(G), we define CFI T (G) to be the vertex-colored graph obtained from G in the following way. Hence, applying the above construction to a specific graph G yields a pair of nonisomorphic graphs CFI(G) = CFI ∅ (G) and CFI x (G) = CFI {e} (G) for some e ∈ E(G). ▶ Theorem 6.7 (Dawar and Richerby [12]). Let G be a connected graph such that tw(G) ≥ k+1 and deg(v) ≥ 2 for all v ∈ V (G). Then CFI(G) ≃ k CFI x (G).
The strategy to obtain a good lower bound is to find graphs G for which we can show a sufficiently strong upper bound on the treewidths of CFI(G) and CFI x (G). Here, we first provide an analysis for the simple case that G is an (n × n)-grid. This almost achieves the lower bound stated in Theorem 6.1. Then, we argue how to modify the grid to obtain the desired improvement.
For n ≥ 2, let G n,n be the (n × n)-grid. Moreover, let G + n,n be the (n × n)-grid in which each edge is replaced with a path of length 3. Formally, V (G n,n ) = [n] × [n] and ▶ Lemma 6.8. Let n ≥ 2. Then there is a tree decomposition (T, β) of G + n,n of width n + 2 such that

|β(t) ∩
Proof. In order to describe the bags of the tree decomposition, we start by defining several (see also Figure 6.2). Let j), (i + 1, j)), ((i + 1, j), (i, j))}, (Formally, the sets defined above may also contain elements outside of V (G + n,n ) if some index is not contained in the set [n]. In this case, we simply do not include the corresponding element in the set.) Now define Also set Observe that each bag contains at most n + 3 elements. It remains to define the edges of the tree T . The following edges are added to the set E(T ): , and t B n,j t C 1,j+1 for all j ∈ [n − 1]. It can be verified in a straight-forward manner that (T, β) defines a tree decomposition of the graph G + n,n with the desired properties. ◀ ▶ Lemma 6.9. Let n ≥ 2. Then tw(CFI(G n,n )) ≤ 2n + 5 and tw(CFI x (G n,n )) ≤ 2n + 5.
This concludes the proof. ◀ Combining Lemma 6.9 and Theorem 6.7, we almost obtain the lower bound stated in Theorem 6.1. By slightly modifying the constructions presented above, we are able to improve on the upper bound of the treewidth of certain Cai-Fürer-Immerman graphs. Towards this end, let G ′ n,n be the graph obtained from G n,n by replacing each vertex of degree 4 with two vertices of degree 3 as indicated in Figure 6.3. Formally,  Note that G n,n is a minor of G ′ n,n and thus, tw(G ′ n,n ) ≥ n. Also, let G * n,n be the graph obtained from G ′ n,n by replacing each edge with a path of length 3. Formally, we construct the graph G * n,n from G + n,n as follows.
The graph resulting from applying the modification for all i, j ∈ {2, . . . , n − 1} is G * n,n .
▶ Lemma 6.10. Let n ≥ 2. Then there is a tree decomposition (T, β) of G * n,n of width n + 1 such that In this case, t is a leaf of T , and β(s) ∩ V (G n,n ) = ∅ for the unique s ∈ V (T ) with st ∈ E(T ).
Proof. We only describe how to modify the decomposition from Lemma 6.8. We replace the nodes t A i,j and t D i,j with five nodes
The proof is literally the same as for Lemma 6.9 using Lemma 6.10 instead of Lemma 6.8.
▶ Theorem 6.12. For every k ≥ 2, there are non-isomorphic graphs G k and H k of treewidth at most 2k + 5 such that G k ≃ k H k .
Proof. Let G k := CFI(G ′ k+1,k+1 ) and H k := CFI x (G ′ k+1,k+1 ). Then the statement follows from Theorem 6.7 and Lemma 6.11. ◀ ▶ Remark 6.13. The graphs G k and H k constructed in Theorem 6.12 are vertex-colored. It is possible to turn them into uncolored graphs by using simple gadgets to encode the vertex colors (see, e.g., [6]). We remark that these gadgets can be constructed in such a way that the treewidth of G k and H k as well as indistinguishability by k-WL is preserved. Hence, Theorem 6.12 remains valid even when we restrict ourselves to uncolored graphs.
As a corollary from Theorems 6.4 and 6.12, we obtain Theorem 6.1.

Conclusion
We have proved that for k ≥ 2, the algorithm k-WL implicitly computes the decomposition of its input graph into its triconnected components. As a by-product, we found that every connected constituent graph of an association scheme is either a cycle or 3-connected.
We have applied this insight to improve on the upper bound on a parametrization of the WL dimension of a graph by its treewidth and have also provided a lower bound that is asymptotically only a factor of 2 away from the upper bound. Naturally, it would be nice to further close the gap between the upper and the lower bound. We remark that some improvements on the lower bounds are possible for small values of k as indicated in Table 1. For k ≥ 2, the WL dimension of the class T k is at least 2, since 1-WL does not distinguish between the cycle C 6 of length 6 and the disjoint union of two triangles 2K 3 . Observe that tw(C 6 ) = tw(2K 3 ) = 2. Applying the Cai-Fürer-Immerman construction to the complete graph K 4 and calculating the treewidth of the resulting graph by computer [39], we also found that 2-WL does not identify every graph of treewidth 8.
It is an interesting open problem to determine dim WL (T 3 ). A potential approach for improving the upper bound could be to argue that 2-WL implicitly computes a tree decomposition with certain nice properties. Observe that, by Theorem 5.7, it essentially suffices to solve the problem for 3-connected graphs.
Indeed, more generally, a natural use case of our results may be determining the WL dimension of certain graph classes that satisfy the requirements of Theorem 5.7. For example, we conjecture that 2-WL identifies every planar graph. Using the results of this paper, it essentially suffices to show this for 3-connected planar graphs. In fact, we show that the decomposition (T, β) and the color sets to prove that 2-WL implicitly computes (T, β) can be chosen such that C bags and C edges only depend on the equivalence class of the graph G with respect to 2-WL. More precisely, for a second graph G ′ which 2-WL does not distinguish from G, we show that we can take the same sets C bags and C edges as for G.
We fall back on the concepts and notation described in [31, Section 3], which we recapitulate for completeness.
For a graph G, define the set P (G) to consist of the pairs (S, K), where S is a separator of G of minimum cardinality and K is the vertex set of a connected component of G − S. Let P 0 (G) be the set of minimal elements of P (G) with respect to the following (well-defined) partial order ≤ on P (G): The following lemma summarizes useful properties of P (G) when certain bounds on the connectivity and the vertex degrees hold in G.
We intend to prove Theorem 5.6 via an induction on the order of G. To this end, we need a method to remove the vertices appearing in the second component of pairs in P 0 (G) from the graph in an isomorphism-invariant fashion.
For a set S ⊆ V (G), define G S ⊤ as the graph on the vertex set These concepts also play a crucial role in the proof of Theorem 5.7. In order to allow for an induction, we use the initial coloring λ of G to define also colorings of the graphs G S ⊤ . For an arc coloring λ of G, we obtain an arc coloring λ S ⊤ for G S ⊤ as follows.
If G is a vertex-colored graph with vertex coloring λ ′ , in order to obtain a coloring of G S ⊤ , we define an arc coloring λ as λ(v 1 , v 2 ) := λ ′ (v 1 ) and let λ S ⊤ be as above. For (S, K) ∈ P 0 (G), we also let G Finally, we define G ⊥ to be the graph with vertex set K and edge set Given an arc coloring λ of a graph G that is not 3-connected, we define an arc coloring λ ⊥ of G ⊥ as follows. Assume that v 1 . v2) ) is the isomorphism class of the colored graph (G S ⊤ , λ S ⊤ ) (v1,v2) which is obtained from (G S ⊤ , λ S ⊤ ) by individualizing v 1 and v 2 . Therefore, the graphs We define the rooted tree decomposition from Theorem 5.6 by induction on the order of G. If G is 3-connected or a cycle (which includes the case |V (G)| = 1), the graph T consists of a single node t and we let β(t) := V (G). Clearly, 2-WL implicitly computes (T, β) and the sets C bags and C edges are canonical for every 2-WL-equivalence class of graphs (C bags consists of all colors in the image of χ G and C edges is empty).
If G is not 3-connected, G contains at least one separator of size at most 2. To construct (T, β) and show that 2-WL implicitly computes it, we distinguish cases according to the vertex degrees and connectivity in G.
First suppose that G is not 2-connected, i.e. G contains a cut vertex. Since G ⊥ is smaller than G, there is a rooted tree decomposition (T ⊥ , β ⊥ ) for it with the desired properties by the induction hypothesis. To construct (T, β) from (T ⊥ , β ⊥ ), consider for an ({s}, K) ∈ P 0 (G) the graph G that is closest to the root and satisfies s ∈ β ⊥ (t)}.
Finally, set Clearly, the rooted tree decomposition (T, β) satisfies the first two conditions from Theorem 5.6. We now show that 2-WL implicitly computes it. By [31,Lemma 8], for all u ∈ V (G ⊥ ) and v ∈ V (G) \ V (G ⊥ ), the inequality χ G (u, u) ̸ = χ G (v, v) holds. We conclude that χ G | (V (G ⊥ )) 2 is a stable coloring of G ⊥ (with respect to 2-WL). Hence, by induction, since G ⊥ is smaller than G, there are sets and a r X i v we conclude the existence of a set of colors C edges with the desired properties. Note that C bags and C edges are solely determined by the equivalence class of the graph G with respect to 2-WL. This completes the analysis for the case that G is not 2-connected. Now assume that G is 2-connected, but not 3-connected, that is, every minimal separator of G has size 2. Similar to the analysis in [31], we need to distinguish two further cases depending on the minimum degree in G. More precisely, in order to be able to apply Lemma A.1, we require that G has minimum degree 3. Hence, we first cover the case that G has minimum degree 2. (Note that G does not contain a vertex of degree 1 since G is 2-connected.) Let D := {v ∈ V (G) | deg(v) = 2} and, overwriting G ⊥ for this case, define ] to be the torso on the remaining vertices. By the induction hypothesis, there is a tree decomposition (T ⊥ , β ⊥ ) for the graph G ⊥ with the desired properties. We construct (T, β) from (T ⊥ , β ⊥ ) as follows. For each connected component C of G[D], we introduce a new node t C with β(t C ) := C ∪ N G (C) and insert the edge (t ′ C , t C ), where t ′ C ∈ V (T ⊥ ) is the unique node that is closest to the root and satisfies N G (C) ⊆ β ⊥ (t ′ C ). Observe that |N G (C)| = 2 and the corresponding pair of vertices in N G (C) forms an edge in G ⊥ , which guarantees the existence of the node t ′ C . Clearly, the decomposition (T, β) satisfies the first two conditions of Theorem 5.6. Hence, it remains to argue that 2-WL implicitly computes (T, β). First observe that χ G (v, v) ̸ = χ G (u, u) holds for all v ∈ D and u ∈ V (G ⊥ ). Since 2-WL knows which edges are inserted to obtain the torso G[[V (G) − D]], the coloring χ G | (V (G ⊥ )) 2 is a stable coloring of G ⊥ with respect to 2-WL. Hence, by the induction hypothesis, there are C ⊥ bags , and hold for all v, w ∈ V (G ⊥ ). Moreover, there is a set C ⊤ bags ⊆ {χ G (v, w) | v, w ∈ V (G)} such that for all v, w ∈ V (G), where C v denotes the connected component of G[D] that contains v (assuming v ∈ D). Hence, setting C bags := C ⊥ bags ∪ C ⊤ bags gives the desired set of colors for the bags of (T, β).
So it remains to express the edges (t ′ C , t C ) for connected components C of G[D] via membership in a set of color classes with respect to 2-WL. Let v ∈ V (G ⊥ ) = V (G) \ D and w ∈ D. Then As in the first case, we conclude the existence of a set of colors C edges with the desired properties. Note that the sets C bags and C edges are solely determined by the equivalence class of the graph G with respect to 2-WL. This completes the case that G is 2-connected and has minimum degree 2. Now suppose that G is 2-connected, but not 3-connected, and has minimum degree at least 3. We first define the rooted tree decomposition (T, β) described in Theorem 5.6. Since G ⊥ is smaller than G, there is a rooted tree decomposition (T ⊥ , β ⊥ ) for it with the desired properties by the induction hypothesis. To construct (T, β) from (T ⊥ , β ⊥ ), we introduce for each (S, K) ∈ P 0 (G) a node t (S,K) . Let M be the collection of all these t (S,K) . Now we define V (T ) := V (T ⊥ ) ⊎ M and E(T ) := E(T ⊥ ) ∪ (t, t (S,K) ) t (S,K) ∈ M and t is the unique node of V (T ⊥ ) that is closest to the root and satisfies S ⊆ β ⊥ (t) and set It is straightforward to see that this decomposition satisfies the first two conditions from Theorem 5.6. To show that 2-WL implicitly computes it, we again need to find sets C bags , C edges ⊆ {χ G (v, w) | v, w ∈ V (G)} such that and We first show statements analogous to Theorem 6 and Corollary 7 from [31] for 2-connected graphs. For k ≥ 2, ℓ ≤ k, and v 1 , . . . , v ℓ ∈ V (G), we use the shorthand χ G,k (v 1 , . . . , v ℓ ) for the color χ G,k (v 1 , . . . , v ℓ , v ℓ , . . . , v ℓ ).
Proof. By Corollary 5.3, we can assume that vertices contained in a 2-separator have different χ k -colors than vertices which are not contained in any 2-separator. Thus, vertex pairs connected via a path which does not contain any vertices of 2-separators obtain different colors than vertex pairs for which every connecting path contains a vertex of a 2-separator. Since K is the vertex set of a connected component of G − S, there is a path in G[K] from u to v. Moreover, by Part 3 of Lemma A.1, no vertex on the path is contained in a 2-separator of G. On the other hand, in G ′ , all paths from u ′ to v ′ must include a vertex of S ′ , since v ′ / ∈ K ′ . We conclude that χ G,k (u, v) ̸ = χ G ′ ,k (u ′ , v ′ ). ◀ ▶ Lemma A.4. Assume k ≥ 2 and let G and G ′ be 2-connected graphs of minimum degree at least 3 that are not 3-connected. Then for Proof. Let G, G ′ , v, v ′ be as described in the prerequisites of the lemma. By Part 3 of Lemma A.1, the vertex v ′ is not contained in any 2-separator of G ′ . If v is contained in a 2-separator of G, by Corollary 5.3, the algorithm k-WL distinguishes v from v ′ . Hence, we can assume otherwise.
We show that there are exactly two vertices each of which is contained in a 2-separator and can be reached from v ′ via a path that does not use any other vertices contained in 2-separators, while this is not the case for v.
Since v ′ ∈ V (G ′ ) \ V (G ′ ⊥ ), there must be a 2-separator S ′ and a connected component of G ′ − S ′ with vertex set K ′ with (S ′ , K ′ ) ∈ P 0 (G ′ ) and v ′ ∈ K ′ . Furthermore, since G ′ is connected and S ′ is a separator of minimal size, there must be a path in G ′ [S ′ ∪ K ′ ] from v ′ to each of the two vertices contained in S ′ . Each path can be chosen to avoid the other vertex in S ′ : otherwise, there would be a cut vertex in G ′ , contradicting its 2-connectedness. This means that for the two chosen paths, all but the last vertex are contained in K ′ . In particular, by Part 3 of Lemma A.1, none of these inner path vertices is contained in a 2-separator. Note that all vertices reachable from v ′ in G ′ − S ′ are in K ′ and thus, there are exactly two vertices that each are contained in a 2-separator and can be reached from v ′ via a path that does not use any other vertices contained in 2-separators.
We now show that there are at least three vertices that are contained in a 2-separator and can be reached from v via a path that does not use any other vertices contained in 2-separators. Choose (S, K) ∈ P (G) such that v ∈ K. Lets 1 be one of the vertices in S. Then there is a path from v tos 1 . Let s 1 be the first vertex on the path that is contained in a 2-separator. Its existence is guaranteed becauses 1 is a candidate.
Chooses 2 such that {s 1 ,s 2 } forms a 2-separator of G. Since s 1 is not a cut vertex, there must be a path from v tos 2 that avoids s 1 . Again, let s 2 be the first vertex on the path that is contained in a 2-separator. Now, two cases can occur. In the first case, {s 1 , s 2 } is not a 2-separator. Then there is a vertexs 3 such that {s 1 ,s 3 } is a 2-separator and such that there is a path from v tos 3 in G − {s 1 , s 2 }. Choose s 3 as the first vertex on the path that is contained in a 2-separator.
Since G[K] is connected, there is a path in G[K] from v tos 3 . Let s 3 be the first vertex on the path contained in a 2-separator.
In both cases, we have found three vertices s 1 , s 2 , s 3 that each are contained in a 2separator and such that every s i is reachable from v via a path that avoids all vertices contained in 2-separators except for s i .
This property distinguishes v and v ′ and is detectable by k-WL. As a result, we obtain that χ G,k (v, v) ̸ = χ G ′ ,k (v ′ , v ′ ). ◀ By Lemma A.4, the color set computed by 2-WL for vertices in V (G ⊥ ) is disjoint from the set of colors for vertices in V (G) \ V (G ⊥ ). Since 2-WL also knows which edges are added to obtain the torso G ⊥ = G[[V (G ⊥ )]], we conclude that χ G | (V (G ⊥ )) 2 is a stable coloring of G ⊥ (with respect to 2-WL). Thus, by the induction hypothesis, since G ⊥ is smaller than G, there are sets C ⊥ bags , C ⊥ edges ⊆ {χ G (v, w) | v, w ∈ V (G)} such that and χ G (v, w) ∈ C ⊥ edges ⇔ (t v , t w ) ∈ E(T ) hold for all v, w ∈ V (G ⊥ ) ⊆ V (G). Moreover, by Lemmas A.3 and A.4, there is a set holds for all vertices v, w ∈ V (G), where K w is chosen such that there are vertices u ′ , v ′ for which ({u ′ , v ′ }, K w ) ∈ P 0 (G) and w ∈ K w . Hence, C bags := C ⊥ bags ∪ C ⊤ bags gives the desired set of colors for the bags of (T, β).
containing every graph isomorphic to G, G ′ , or a minor of one of them, it suffices to show the statement for the case that G and G ′ are 2-connected.
If G and G ′ do not have the same minimum degree, they are distinguished by their degree sequences. Now first suppose both G and G ′ have minimum degree at least 3.
By Corollary B.4, the partition of the vertices and arcs induced by the coloring χ G,k restricted to V (G ⊥ ) is finer than the partition induced by λ ⊥ . Also, by Lemma A.4, vertices in V (G ⊥ ) obtain different colors than vertices in V (G) \ V (G ⊥ ). Similar statements hold in G ′ .
By [31,Lemma 15], the case that G and G ′ do not have minimum degree at least 3 reduces to the case of minimum degree at least 3, letting G from the lemma be the class of graphs containing every graph isomorphic to G, G ′ , or a minor of one of them. ◀