The Weisfeiler-Leman Dimension of Planar Graphs is at most 3
Sandra Kiefer Ilia Ponomarenko Pascal Schweitzer






The Weisfeiler-Leman Dimension of Planar Graphs is at most 3
    Sandra Kiefer

RWTH Aachen University

kiefer@informatik.rwth-aachen.de
Ilia Ponomarenko 

Petersburg Department of V. A. Steklov 
Institute of Mathematics

inp@pdmi.ras.ru
Pascal Schweitzer

RWTH Aachen University 

schweitzer@informatik.rwth-aachen.de
    Received:  ; accepted:  
=================================================================================================================================================================================================================================================================



This is an extended version of the paper with the same title published in the Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science <cit.>.


We prove that the Weisfeiler-Leman (WL) dimension of the class of all finite planar graphs is at most 3. In particular, every finite planar graph is definable in first-order logic with counting using at most 4 variables. The previously best known upper bounds for the dimension and number of variables were 14 and 15, respectively.

First we show that, for dimension 3 and higher, the WL-algorithm correctly tests isomorphism of graphs in a minor-closed class whenever it determines the orbits of the automorphism group of any arc-colored 3-connected graph belonging to this class.

Then we prove that, apart from several exceptional graphs (which have WL-dimension at most 2), the individualization of two correctly chosen vertices of a colored 3-connected planar graph followed by the 1-dimensional WL-algorithm produces the discrete vertex partition. This implies that the 3-dimensional WL-algorithm determines the orbits of a colored 3-connected planar graph.

As a byproduct of the proof, we get a classification of the 3-connected planar graphs with fixing number 3.













§ INTRODUCTION


The Weisfeiler-Leman algorithm (WL-algorithm) is a fundamental algorithm used as a subroutine in graph isomorphism testing. More precisely, it constitutes a family of algorithms. For every positive integer k there is a k-dimensional version of the algorithm that colors all k-tuples of vertices in two given undirected input graphs and iteratively refines the color classes based on information of previously obtained colors. 

The algorithm has surprisingly strong links to notions that seem unrelated at first sight. For example, there is a precise correspondence to Sherali-Adams relaxations of certain linear programs
<cit.>, there are duplicator-spoiler games capturing the same information as the algorithm <cit.>, it is related to separability of coherent configurations <cit.>, and there is a close correspondence between the algorithm and first-order logic with counting (C^k). More precisely, for two graphs G and G', if the integer k is the smallest dimension such that the k-dimensional WL-algorithm distinguishes two graphs, then k+1 is the smallest number of variables of a sentence in first-order logic with counting distinguishing the two graphs <cit.>. 

Exploiting these correspondences, the seminal construction of Cai, Fürer and Immerman <cit.> shows that there are examples of pairs of graphs on n vertices for which a dimension of Ω(n) is required for the WL-algorithm to distinguish the two graphs.

However, for various graph classes a bounded dimension suffices to distinguish every two non-isomorphic graphs from each other. While typically not very practical due to large memory consumption, this yields a polynomial-time algorithm to test isomorphism of graphs from such a class.
 In a tour de force, Grohe shows that for all graph classes with excluded minors a bounded dimension of the WL-algorithm suffices to decide graph isomorphism <cit.>.
 
An ingredient in Grohe's proof deals with the special case of the class of planar graphs, for which a bound on the necessary dimension of the WL-algorithm had been proven earlier by Grohe separately <cit.>. Thus, there is a k such that the k-dimensional WL-algorithm distinguishes every two non-isomorphic planar graphs from each other. In his Master's thesis <cit.> (see <cit.>), Redies analyses Grohe's proof showing that this k can be chosen to be 14. For 3-connected planar graphs it was also shown earlier by Verbitsky <cit.> that one can additionally require the quantifier rank to be logarithmic. Feeling that this is far from optimal, Grohe asked in his book <cit.> and also at the 2015 Dagstuhl meeting on the graph isomorphism problem <cit.> for a tight k.
In this paper we show that k=3 is sufficient.



We say that a graph is identified by the k-dimensional WL-algorithm if the algorithm distinguishes the graph from all other graphs.
Following Grohe <cit.>, we say that a graph class 𝒞 has WL-dimension k if k is the smallest integer such that all graphs in 𝒞 are identified by the k-dimensional WL-algorithm. With this terminology our main theorem reads as follows.




 The Weisfeiler-Leman dimension of the class of planar graphs is at most 3.

(Equivalently, every planar graph is definable by a sentence in first-order logic with counting that uses only 4 variables.)
 
 
Our proof is separated into two parts. The first part (Sections <ref>–<ref>) constitutes a reduction from general graphs to 3-connected graphs, while the second part (Section <ref>) handles 3-connected planar graphs.

In the first part, which does not only concern planar graphs, we start by showing that for a hereditary graph class 𝒢, 
for k ≥ 2, if the k-dimensional WL-algorithm distinguishes every two vertex-colored non-isomorphic 2-connected graphs from each other, then it distinguishes every two non-isomorphic graphs in 𝒢
(Theorem <ref>).

While it is tempting to believe that when requiring k≥ 3 a similar statement can be made about 3-connected graphs, we need the additional assumption that 𝒢 is minor-closed. In fact, our proof also needs a more technical requirement that the WL-algorithm correctly determines the vertex orbits.

We can then argue that if 𝒢 is additionally minor-closed, for k ≥ 3, if the k-dimensional WL-algorithm correctly determines orbits on all arc-colored 3-connected graphs in 𝒢, then it distinguishes every two non-isomorphic graphs in 𝒢 from each other (Theorem <ref>).

To prove these two reductions, we employ several structural observations on decomposition trees. These allow us to cut off isomorphism-invariantly the leaves of the decomposition trees of 2- and 3-connected components, respectively. This can be done implicitly without having to explicitly construct the corresponding decomposition trees (see Section <ref>).

In the second part we show that the 3-dimensional WL-algorithm identifies all (arc-colored) 3-connected planar graphs. More precisely, we argue that orbits are determined, as required by our reduction. 
In fact, we show a stronger statement in that we do not need the full power of the 3-dimensional WL-algorithm. Using Tutte's Spring Embedding Theorem <cit.>, we argue that if in an arc-colored 3-connected planar graph there are three vertices each with a unique color (so-called singletons) that share a common face then applying the 1-dimensional WL-algorithm (usually called color refinement) yields a coloring of the graph in which all vertices are singletons. Since this would only give us a bound of k=4, we show then that in most 3-connected planar graphs it suffices to individualize 2 vertices to get the same result.
Our proof actually characterizes the exceptions, the graphs in which we need to individualize 3 vertices. We can handle these graphs separately to finish our proof. 

The fixing number of a graph G is the minimum size of a set of vertices S such that the only automorphism that fixes S pointwise is the identity. It follows from generally known facts that the fixing number of a 3-connected planar graph is at most 3. Our proof however shows that the only 3-connected planar graphs with fixing number 3 are those depicted in Figure <ref> (see also Corollary <ref>). The properties of these graphs are summarized in Table <ref>.









normalvertex=[circle,fill=white,draw=black, inner sep = 2.5]






On the algorithmic side we obtain a very easy algorithm to check isomorphism of 3-connected planar graphs. In fact the arguments show that with the right cell selection strategy, individualization refinement algorithms (such as nauty and traces <cit.> or bliss <cit.>), which constitute to-date the fastest isomorphism algorithms in practice, have polynomial running time on 3-connected planar graphs.
 
 
Concerning lower bounds on the WL-dimension of planar graphs, it is not difficult to see that there are planar graphs with WL-dimension 2 (for example the 6-cycle). However, the question whether the maximum dimension of the class of planar graphs is 2 or 3 remains open. 





  
*Related work.

There is an extensive body of work on isomorphism testing of planar graphs. Most notably Hopcroft and Tarjan first exploited the decomposition of a graph into its 3-connected components to obtain an algorithm with quasi-linear running time <cit.>, which led to a linear-time algorithm by Hopcroft and Wong <cit.>. 
More recent results show that isomorphism of planar graphs can be decided in logarithmic space <cit.>.

There are also various results on the descriptive complexity of planar graph isomorphism. In this direction, Grohe shows that fixed-point logic with counting FPC captures polynomial time on planar graphs <cit.> and more generally on graphs of bounded genus <cit.>. This was also known for graphs of bounded tree width <cit.>.

Subsequent work shows that for 3-connected planar graphs and for graphs of bounded tree width it is possible to restrict the quantifier depth (or equivalently, the number of iterations that the WL-algorithm performs until it terminates) to a polylogarithmic number, which translates to parallel isomorphism tests <cit.>. For general graphs, recent results give new upper and lower bounds on the quantifier depth (translating into bounds on the maximum number of iterations of the WL-algorithm) 
<cit.>.
Extending the results on planar graphs in the direction of dynamic complexity, Mehta shows that isomorphism of 3-connected planar graphs is in DynFO+ <cit.>, where in fact no counting quantifiers are required.

While it is possible to describe precisely the graphs of WL-dimension 1 <cit.> (i.e., graphs definable with a 2-variable sentence in first order logic with counting), it appears difficult to make such statements for higher dimensions. However, for various graph classes for which the isomorphism problem is known to be polynomial time solvable, one can give upper bounds on the dimension. 
E.g., for cographs, interval graphs, and, more generally, for rooted directed-path graphs, it suffices to apply the 2-dimensional WL-algorithm in order to decide isomorphism <cit.>. In general, isomorphism of graph classes with an excluded minor can be solved in polynomial time <cit.> and in fact a sufficiently high-dimensional WL-algorithm will decide isomorphism on such a class <cit.>. More strongly, FPC captures polynomial time on graph classes with an excluded minor. 
In the proof of this result, structural graph theory and in particular decompositions play a central role. While our paper  uses very basic parts of these techniques and concepts, they are only implicit and we refer the reader to <cit.> for a more systematic treatment.






§ PRELIMINARIES


All graphs in this paper are finite simple graphs, that is, undirected graphs without loops. The vertex and the edge set of a graph G are denoted by V(G) and E(G), respectively. The neighborhood N(X) of a subset of the vertices X ⊆ V(G) is the set { u∈ V(G)∖ X |∃ v ∈ X  s.t. {u,v}∈ E(G)}. 
For X ⊆ V(G), we denote by G[X] the subgraph of G induced by X, i.e., the graph with vertex set X and edge set E(G) ∩{{ u,v }| u,v ∈ X}.
The graph G-X  G[V(G)∖ X] is obtained from G by removing X. We write G ≅ H to indicate that G is isomorphic to H.
A minor of G is a graph obtained by repeated vertex deletions, edge deletions and edge contractions.

For a positive integer k, a graph G is k-connected if G has more than k vertices and for all X ⊆ V(G) with |X| < k, the graph G - X is connected.
A separator S⊆ V(G) is a subset of the vertices such that G-S is not connected. A vertex v is a cut vertex if {v} is a separator, and a 2-separator is a separator of size 2. 
A 2-connected component of G is a subset S' of V(G) such that the graph G[S'] is 2-connected and such that S' is maximal with respect to inclusion. We refer the reader to <cit.> for more basic information on graphs, in particular on planar graphs, which are graphs that can be drawn in the plane without crossings.

A vertex-colored graph (G, λ) is a graph G with a function λ V →𝒞, where 𝒞 is an arbitrary set. We call λ a vertex coloring of G. Similarly, an arc-colored graph is a graph G with a function λ{(u,u)| u∈ V(G)}∪{ (u,v) |{u,v}∈ E(G)}→𝒞. In this case, we call λ an arc coloring.
We interpret λ(u,u) as the vertex color of u and for {u,v}∈ E(G) we interpret λ(u,v) as the color of the arc from u to v. In particular it may be the case that λ(u,v) ≠λ(v,u). However, while we allow such colorings, all graphs in this paper are undirected. Furthermore, we treat every uncolored graph as a monochromatic colored graph.




  
*The Weisfeiler-Leman algorithm (see <cit.>). For k ∈ℕ, a graph G and a coloring λ of V^k(G), let (v_1, …, v_k) be a vertex k-tuple of G. We define 0χ_G^k (v_1, …, v_k) to be a tuple consisting of an encoding of λ(v_1, …, v_k) and an encoding of the isomorphism class of the colored graph obtained from G[{v_1, …, v_k}] by coloring for i ∈{1, …, k} vertex v_i with color i.


That is, for a second graph G', possibly equal to G, with coloring λ' and for a vertex k-tuple (v_1',…,v_k') of G' we have

    0χ^k_G (v_1, …, v_k) = 0χ^k_G' (v_1', …, v_k')

if and only if λ (v_1, …, v_k) = λ'  (v_1', …, v_k') and there is an isomorphism from G[v_1,…, v_k] to G'[v'_1,…, v'_k] mapping v_j to v'_j for all j∈{1,…,k}. 

We recursively define the color i+1χ^k_G (v_1, …, v_k) by setting

    i+1χ^k_G (v_1, …, v_k)  (iχ^k_G (v_1, …, v_k); ℳ),

where ℳ is the multiset defined as

    ℳ:= {{(iχ^k_G(w,v_2, …, v_k), …, iχ^k_G(v_1, …, v_k-1, w)
    )  | w∈ V     }}

if k ≥ 2 and as ℳ:=  {{ (iχ^1_G(w) | w∈ N(v_1) }} if k = 1. That is, if k = 1, the iteration is only over neighbors of v_1.

There is a slight technical issue about the initial coloring. Suppose for a fixed k we are given a graph G with a coloring λ' of V^ℓ(G) for ℓ < k. To turn it into a correct input for the k-dimensional WL-algorithm, we replace λ' by an appropriate coloring λ. For a vertex tuple (u_1, …, u_k), we define λ (u_1, …, u_k) λ'(u_1, … ,u_ℓ). Note that λ preserves all information from λ'. If λ' is an arc coloring we define λ (u_1, …, u_k) to be (λ'(u_1, u_2),0) if (u_1,u_2) is in the domain of λ' and to be (1,1) otherwise.

By definition, the coloring i+1χ^k_G induces a refinement of the partition of the k-tuples of the vertices of the graph G with coloring iχ^k_G. Thus, there is some minimal i such that the partition induced by the coloring i+1χ^k_G is not strictly finer than the one induced by the coloring iχ^k_G on G. For this minimal i, we call iχ^k_G the stable coloring of G and denote it by χ^k_G. 

For k ∈ℕ, the k-dimensional WL-algorithm takes as input a vertex coloring or an arc coloring λ of a graph G and returns the coloring χ^k_G. For two graphs G and G', we say that the k-dimensional WL-algorithm distinguishes G and G' if its application to each of them results in colorings with differing color class sizes. More precisely, the graphs G and G' are distinguished if there is a color C in the range of χ^k_G such that the sets
{v̅|v̅∈ V^k(G), χ^k_G(v̅) = C} and {w̅|w̅∈ V^k(G'), χ^k_G'(w̅) = C} have different cardinalities.


If two graphs are distinguished by the k-dimensional WL-algorithm for some k, then they are not isomorphic. However, if k is fixed, the converse is not always true. There is a close connection between the WL-algorithm and first-order logic with counting (as well as fixed-point logic with counting). We refer the reader to existing literature (for example <cit.>) for more information.

For improved readability, we will use the letter λ to denote arbitrary colorings that do not necessarily result from applications of the WL-algorithm.







§ DECOMPOSITIONS


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 ⊆ V(G)∖ S is the vertex set of a connected component of G-S.

We observe that if G is a connected graph that is not 2-connected, then P(G) is the set of pairs ({s},K) where s is a cut vertex and G[K] a connected component of G- {s}. In this case we also write (s,K) instead of ({s},K). If G is 2-connected but not 3-connected, all separators in P(G) have size 2.

There is a natural partial order on P(G) with respect to inclusion in the second component, i.e., we can define:

    (S,K) ≤ (S',K')  K ⊆ K'.



We define P_0(G) to be the set of minimal elements of P(G) with respect to this partial order.


It immediately follows from the definitions that the sets P(G) and P_0(G) (and the corresponding partial orders) are isomorphism-invariant (i.e., preserved under isomorphisms).




 Note that P_0(G) is non-empty whenever G is not a complete graph. Also note that if G is not 2-connected, then for two distinct minimal elements (S,K) and (S',K') in P_0(G) we have K ∩ K' = ∅. Furthermore, in the case that G is connected but not 2-connected, the set P_0(G) contains exactly the pairs (s,K) for which s is a cut vertex and G[K] a connected component of G-{s} that does not contain a cut vertex of G. 
These two observations can be generalized to graphs with a higher connectivity, but for this we need an additional requirement on the minimum degree as follows.


Let G be a graph that is not (k+1)-connected and has minimum degree at least 3k-1/2. 


  * 
If (S,K)∈ P_0(G) and (S',K')∈ P(G) are distinct, then K⊆ K' or (K∪ S)∩ (K'∪ S') = S∩ S'.

  * If (S,K),(S',K') ∈ P_0(G) are distinct, then (K∪ S)∩ (K'∪ S') = S∩ S'.

  * A pair (S,K)∈ P(G) is contained in P_0(G) if and only if there is no separator S' of G of minimum cardinality with S'∩ K ≠∅.




 (Part <ref>)
Assume that (S,K)∈ P_0(G) and (S',K')∈ P(G) are distinct. Note that S = N(K) and S' = N(K') since S and S' are minimal separators.

Suppose K ⊈K' and that there exists v ∈ K ∩ K'. Then v has a neighbor u ∈ K which does not belong to K'. Since v ∈ K', this implies that u belongs to S'. Therefore, the graph G-u is at most (k-1)-connected. On the other hand, u lies in K. By Corollary 1 in <cit.>, the graph G-u is k-connected, yielding a contradiction.

(Part <ref>) This follows by applying Part <ref> twice.


(Part <ref>) If (S,K)∈ P(G) is not minimal then there is (S',K')∈ P(G) with K'⊊ K. Then S'⊆ K∪ S but S≠ S', which shows that S'∩ K≠∅. Conversely, suppose (S,K)∈ P_0(G) and that there is a minimum size separator S' of G with S'∩ K≠∅. Let K' ⊆ V(G-S') be a vertex set such that G[K'] is a connected component of G-S'.
Then (S,K) and (S',K') violate Part <ref> of the lemma.


We remark that for a connected graph G which is not 3-connected, the elements of P_0(G) correspond to the leaves in a suitable decomposition tree (i.e., the decomposition into 2- or 3-connected components) in the sense of Tutte. 
However, we will not require this fact.

In the following we present a method to remove the vertices appearing in the second component of pairs in P_0 from graphs in such a way that the property whether two graphs are isomorphic is preserved. This will allow us to devise an inductive isomorphism test. In the next sections we will then show that a sufficiently high-dimensional WL-algorithm in some sense implicitly performs this induction. 




For a graph G and a set S ⊆ V(G), we define the graph G^S_⊤ as consisting of the vertices of S and those appearing together with S in P_0(G). More precisely,
G^S_⊤ is the graph on the vertex set 
    V'= S ∪⋃_(S,K)∈ P_0(G) K

 with edge set E' = E(G[V']) ∪{{s,s'}| s,s'∈ S  and s≠ s'}, see Figure <ref> left and bottom right.[For the reader familiar with tree decompositions we remark that this graph corresponds to the torso of the bag S∪ K in a suitable tree decomposition. However, we will not require this point of view in the paper.] Note that if S is not a separator or does not appear as a separator in P_0(G), then V'=S.


invclip/.style=clip,insert path=[reset cm]
      (-16383.99999pt,-16383.99999pt) rectangle (16383.99999pt,16383.99999pt)
    


For an arc coloring λ of G, we define an arc coloring λ^S_⊤ for the graph G^S_⊤ as follows:

    λ^S_⊤(v_1,v_2)  
    (0,0)   if {v_1, v_2}⊆  S  and {v_1, v_2}∉ E(G)
     
    (λ(v_1,v_2),1)   if {v_1, v_2}⊆  S  and {v_1, v_2}∈ E(G) 
     
    (λ(v_1,v_2),2)    otherwise.


If G is a vertex-colored graph with vertex coloring λ', in order to obtain a coloring for 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 define G^(S,K)_⊤ G^S_⊤[S ∪ K], which differs from G^S_⊤ in that only vertices from S and K are retained. Again we define a coloring λ^(S,K)_⊤ which is simply the restriction of λ^S_⊤ to pairs (v_1,v_2) for which v_1,v_2∈ S∪ K.

Given a graph G, we define G_ (see Figure <ref> left and top right) to be the graph with vertex set 
    V_ V(G) ∖(⋃_(S,K)∈ P_0(G)K),

and edge set 
 
    E_ E(G[V_])  ∪ {{s_1,s_2}|∃ (S,K)∈ P_0(G)  s.t.  s_1,s_2∈ S, s_1≠ s_2}.

We observe that if G is not 2-connected then G_ is equal to G[V_]. In general, if for some k the graph G is not (k+1)-connected but has minimum degree at least 3k-1/2, then Lemma <ref> applies. In particular, the various components whose vertex sets appear in P_0(G) are disjoint. If G is not 3-connected, this implies that G_ is a minor of G.

In the following we restrict our discussions to graphs that are not 3-connected. Given an arc coloring λ of G we define an arc coloring λ_ of G_ as follows. Assume that v_1, v_2 ∈ V(G_). Let S {v_1,v_2}.

If S is a 2-separator of G but S ∉ E(G), we set

    λ_(v_1,v_2)    (0, ((G^S_⊤,λ^S_⊤)_(v_1,v_2))) .
    Furthermore, if v_1 = v_2 or if {v_1,v_2}∈ E(G) we setλ_(v_1,v_2)    (λ(v_1,v_2), ((G^S_⊤,λ^S_⊤)_(v_1,v_2))),

where by ((G^S_⊤,λ^S_⊤)_(v_1,v_2))  we denote the isomorphism class of the colored graph (G^S_⊤,λ^S_⊤)_(v_1,v_2) obtained from the arc-colored graph (G^S,λ^S_⊤) by individualizing v_1 and v_2. Thus (G^{v_1,v_2}_⊤,λ^{v_1,v_2}_⊤)_(v_1,v_2) and (G'^{v'_1,v'_2}_⊤,λ'^{v'_1,v'_2}_⊤)_(v'_1,v'_2) have the same isomorphism type if and only if there is an isomorphism from the first graph to the second mapping v_1 to v'_1 and v_2 to v'_2. Note that by definition, the λ_-colors of 2-separators of G are distinct from those of other pairs of vertices.

If not stated otherwise, we implicitly assume that for a graph G with initial coloring λ, the corresponding graph G_ is a colored graph with initial coloring λ_.


For k∈{1,2}, if G and G' are k-connected graphs that are not (k+1)-connected and that are of minimum degree at least 3k-1/2 with arc colorings λ and λ', respectively, then

    (G, λ) ≅ (G', λ')  ⟺ (G_, λ_) ≅ (G'_,λ'_).
 



(⟹) Suppose that φ is an isomorphism from (G, λ) to (G', λ'). Since P_0(G) is isomorphism-invariant (Remark <ref>), we know that φ(V(G_))= V(G'_). We claim that φ induces an isomorphism from (G_, λ_) to (G'_,λ'_).
For this it suffices to observe that the definitions of G_ from G and λ_ from λ are isomorphism invariant.

(⟸)
Conversely suppose φ is an isomorphism from the graph (G_, λ_) to (G'_,λ'_). Let {S_1,…,S_t}{S|∃(S,K)∈ P_0(G)} be the set of separators that appear in P_0(G).
Since φ respects the colorings λ_ and λ'_ we can conclude that

    {φ(S_1),…,φ(S_t)}=  {S|∃(S,K)∈ P_0(G')}.

For each j∈{1,…,t} we choose an isomorphism φ_j from G^S_j_⊤ to G'^φ(S_j)_⊤ that maps each s∈ S_j to φ(s)∈φ(S_j). We know that such an isomorphism exists because φ respects the colorings λ_ and λ'_.
We define a map φ from (G, λ) to (G', λ') by setting

    φ(v)φ(v)     if v ∈ V(G_)
    φ_j(v)     if there is a set K⊆ V(G) with v∈ K and (S_j,K)∈ P_0(G).
 
This map is well-defined since by Parts <ref> and <ref> of Lemma <ref> the elements in the second components of pairs in P_0(G) are disjoint and not contained in V(G_). Moreover, the map is an isomorphism, since it respects all edges. Finally, by construction, it also respects the colors of vertices and arcs.





§ REDUCTION TO VERTEX-COLORED 2-CONNECTED GRAPHS


It is easy to see that for a hereditary graph class 𝒢 and k ≥ 2, the k-dimensional WL-algorithm distinguishes all (vertex-colored) graphs in 𝒢 if it distinguishes all (vertex-colored) connected graphs in 𝒢. (By a vertex-colored graph from 𝒢 we mean more precisely a colored graph whose underlying uncolored graph lies in 𝒢.) For this, one simply has to observe that for two non-isomorphic connected components, the sets of colors which the WL-algorithm computes for their vertices are disjoint. 

In this section we show a stronger statement replacing the assumption on connected graphs by an assumption on 2-connected graphs as follows. 


 Let 𝒢 be a hereditary graph class. If, for k ≥ 2, the k-dimensional Weisfeiler-Leman algorithm distinguishes every two non-isomorphic 2-connected vertex-colored graphs (H, λ) and (H', λ') with H, H' ∈𝒢 from each other, then the k-dimensional Weisfeiler-Leman algorithm distinguishes all non-isomorphic graphs in 𝒢.


For the rest of this section, let 𝒢 be a hereditary graph class. Recall that for a graph G ∈𝒢 with an initial vertex coloring or arc coloring λ, the coloring χ^k_G is the stable k-tuple coloring produced by the k-dimensional WL-algorithm on (G,λ).

For ℓ vertices u_1, …, u_ℓ with ℓ < k, we define

    χ^k_G (u_1, …, u_ℓ) χ^k_G (u_1, …, u_ℓ, u_ℓ, …, u_ℓ_k-ℓ times)

to be the coloring of the k-tuple resulting from extending the ℓ-tuple by repeating k-ℓ times its last entry.


To prove Theorem <ref>, we first show that the 2-dimensional WL-algorithm distinguishes pairs of vertices that lie in a common 2-connected component from pairs that do not.


Assume k ≥ 2 and let G, H be two graphs. 
Let u and v be vertices from the same 2-connected component of G and let u' and v' be vertices that are not contained in a common 2-connected component of H. Then χ^k_G(u,v) ≠χ^k_H(u',v').



To improve readability, in this proof we omit the superscripts k, i.e., we write χ_G and χ_H instead of χ^k_G and χ^k_H, respectively. 

For an integer i and vertices x,y denote by W_i(x,y) the number of walks of length exactly i from x to y. (It will be clear from context in which graph we count the number of walks.)
By induction on i, it is easy to see that for k≥ 2 it holds that W_i(x,y)≠ W_i(x',y') implies χ_G(x,y)≠χ_H(x',y') (<cit.>).
  Thus, it suffices to show that for some i, we have W_i(u,v) ≠ W_i(u',v'). Since u' and v' are not contained in the same 2-connected component, there is some cut vertex w' such that every walk from u' to v' passes w'. Suppose that there does not exist a vertex w such that for all i the following hold: 
 
  
  *  W_i(u,w) = W_i(u',w')
  
  *  W_i(w,w) = W_i(w',w')
  
  *  W_i(w,v) = W_i(w',v').
 

Then for every vertex w it holds that χ_G(u,w) ≠χ_H(u',w') or χ_G(w,w) ≠χ_H(w',w') or χ_G(w,v) ≠χ_H(w',v'). If χ_G(w) ≠χ_H(w'), then χ_G(u,w) ≠χ_H(u',w') and thus, for every vertex w it holds that χ_G(u,w) ≠χ_H(u',w') or χ_G(w,v) ≠χ_H(w',v'). 
In other words, there is no vertex w such that ( χ_G(w,v),χ_G(u,w)) = (χ_H(w',v'),χ_H(u',w')). By the definition of the WL-algorithm this implies that χ_G(u,v) ≠χ_H(u',v').  
 
 Now suppose that there is a vertex w such that for all i Conditions 1, 2 and 3 hold. Then for every i the number of walks of length i from u to v which pass w equals the number of walks from u' to v' which pass w'. However, there must be a walk from u to v which avoids w. Let d be its length. We have W_d(u,v) > W_d(u',v') and thus χ_G(u,v) ≠χ_H(u',v').


Next we argue that for k ≥ 2, the k-dimensional WL-algorithm distinguishes cut vertices from other vertices.


 Let k ≥ 2 and assume G, H
 are connected graphs.
 Let w∈ V(G) and w'∈ V(H) be vertices such that G - {w} is connected and H - {w'} is disconnected. Then χ^k_G(w) ≠χ^k_H(w').



Let u' and v' be two neighbors of w' not sharing a common 2-connected component in H. Note that such vertices do not exist for w in G. 

It suffices to show that for all u ∈ V(G) it holds that χ^k_G(u,w) ≠χ^k_H(u',w'). By Theorem <ref>, the color χ^k_H(u',w') encodes that there is v' which is a neighbor of w' and which is not contained in the same 2-connected component as u'. For u and w, such a vertex does not exist in G.


We prove Theorem <ref> by induction over the sizes of the input graphs. The strategy is to show that on input (G, λ) the WL-algorithm implicitly computes the graph (G_⊥, λ_⊥) and to then apply Lemma <ref>. 




	Let k ≥ 2 and assume G, H are connected graphs that are not 2-connected. For vertices v ∈ V(G_⊥) and w ∈ V(H) ∖ V(H_⊥) we have χ^k_G(v) ≠χ^k_H(w).



Note that for a connected but not 2-connected graph G, a vertex v∈ V(G) is in V(G_⊥) if and only if it is a cut vertex or there are at least two cut vertices that lie in the same 2-connected component as v. The equivalent statement holds for H. If v is a cut vertex of G, then the lemma follows immediately from Corollary <ref>.

If v is not a cut vertex, then there are at least two cut vertices u and u' lying in the same 2-connected component as v. Note that there are no such two vertices for w. By Corollary <ref>, u and u' obtain colors distinct from colors of non-cut vertices. Thus, also the colors χ^k_G(v,u) and χ^k_G(v,u') are distinct from all colors of edges from v to non-cut vertices. Moreover, Theorem <ref> yields that the colors χ^k_G(v,u) and χ^k_G(v,u') also encode that v,u,u' all share a common 2-connected component. This information about the existence of such u and u' is contained in the color χ^k_G(v) and thus, χ^k_G(v) ≠χ^k_H(w).




For graphs G, G' ∈𝒢 with vertex colorings λ and  λ', respectively, assume (s,K) ∈ P_0(G) and (s',K') ∈ P_0(G'). For k ≥ 2 suppose the k-dimensional Weisfeiler-Leman algorithm distinguishes all non-isomorphic vertex-colored 2-connected graphs in 𝒢. Assume there is no isomorphism from (G_⊤^(s,K), λ_⊤^(s,K)) to (G_⊤'^(s',K'), λ_⊤'^(s',K')) that maps s to s'. Then

    {χ^k_G(s,v) | v ∈ K}∩{χ^k_G'(s',v') | v' ∈ K'} = ∅.




If χ^k_G(s)≠χ^k_G'(s') then the conclusion of the lemma is obvious. Thus, we can assume otherwise.
We have already seen with Corollary <ref> that cut vertices obtain different colors than non-cut vertices. Thus, we can assume that G and G' are already colored in a way such that s and s'  have a color different from the colors of vertices in K ∪ K'. 

With Theorem <ref> we will now argue that for v∈ K and v'∈ K' we have χ^k_G(v)≠χ^k_G'(v'), which implies the lemma. For readability, we drop the superscripts (s,K) and (s',K'). 
We will show by induction that if the lemma does not hold, then for all u,v ∈ K ∪{s} and all u',v' ∈ K' ∪{s'} with {u,v}⊈{s} and {u',v'}⊈{s'} the following implication is true: 

    iχ_G_⊤^k(u,v) ≠iχ_G'_⊤^k(u',v') ⇒iχ_G^k(u,v) ≠iχ_G'^k(u',v').


For i = 0 the claim follows by definition of the colorings λ_⊤ and λ'_⊤. For the induction step, assume that there exist vertices x,y ∈ K ∪{s}, x',y' ∈ K' ∪{s'} such that {x,y}⊈{s}, {x',y'}⊈{s'}  with iχ_G_⊤^k(x,y) = iχ_G'_⊤^k(x',y') and i+1χ_G_⊤^k(x,y) ≠i+1χ_G'_⊤^k(x',y'). Thus, there must be a color tuple (c_1,c_2) such that the sets

    M    {w | w ∈ V(G_⊤) \{x,y}, (iχ^k_G_⊤(w,y), 
    iχ^k_G_⊤(x,w)) = (c_1,c_2)}and 
    M'    {w' | w' ∈ V(G'_⊤) \{x',y'}, (iχ^k_G'_⊤(w',y'), iχ^k_G'_⊤(x',w')) = (c_1,c_2)}do not have the same cardinality. Let
    D    {(iχ^k_G(w,y), iχ^k_G(x,w)) | w ∈ M}∪{(iχ^k_G'(w',y'), iχ^k_G'(x',w')) | w' ∈ M'}.
 
By induction and by Theorem <ref> 
we have that

    {w | w ∈ V(G) \{x,y}, (iχ^k_G(w,y), iχ^k_G(x,w)) ∈ D}   = M
    and{w' | w' ∈ V(G') \{x',y'}, (iχ^k_G'(w',y'), iχ^k_G'(x',w')) ∈ D}   = M'

and hence these sets do not have the same cardinality. Thus, i+1χ_G^k(x,y) ≠i+1χ_G'^k(x',y'). 

Having shown Implication (<ref>), it suffices to show that 

    {χ^k_G_⊤(s,v) | v ∈ K}∩{χ^k_G'_⊤(s',v') | v' ∈ K'} = ∅.

However, this follows directly from the assumption that the k-dimensional WL-algorithm distinguishes every pair of non-isomorphic vertex-colored 2-connected graphs in 𝒢 and that the graphs (G_⊤^(s,K), λ_⊤^(s,K)) and (G_⊤'^(s',K'), λ_⊤'^(s',K')) are 2-connected.


With this, we can prove the following.
	

Assume k ≥ 2 and suppose the k-dimensional Weisfeiler-Leman algorithm distinguishes all non-isomorphic vertex-colored 2-connected graphs in 𝒢. For two graphs G, G' ∈𝒢 with vertex colorings λ, λ', respectively, suppose s ∈ V(G), s' ∈ V(G'). Assume there is no isomorphism from (G_⊤^s, λ_⊤^s) to (G_⊤'^s', λ_⊤'^s') that maps s to s'. 

Then χ^k_G(s) ≠χ^k_G'(s').



Assume otherwise that χ^k_G(s) = χ^k_G'(s').
Further suppose that

    {K_1,…,K_t}    = {K | (s,K) ∈ P_0(G)}and that{K'_1,…,K'_t'}    = {K' | (s',K') ∈ P_0(G)}.

From (G_⊤^s, λ_⊤^s) ≇(G_⊤'^s', λ_⊤'^s') we conclude that there is a vertex-colored graph (H,λ_H) such that the sets

    I    {j|(G_⊤^(s,K_j), λ_⊤^(s,K_j)) ≅ (H,λ_H)}and
    I'    {j|(G'_⊤^(s',K'_j), λ_⊤'^(s',K'_j)) ≅ (H,λ_H)}

have different cardinalities.
Note that all K_j with j∈ I and all K'_j with j∈ I' have the same cardinality.
We know by Lemma <ref> that for v∈ K_i with i∈ I and v'∈ K_j with j∉ I' we have χ^k_G(s,v)≠χ^k_G'(s',v'). Letting C {χ^k_G(s,v)| i∈ I  and  v∈ K_i}, the vertices s and s' do not have the same number of neighbors connected via an arc of color C.
We conclude that χ^k_G(s) ≠χ^k_G'(s').





	Assume k ≥ 2 and suppose the k-dimensional Weisfeiler-Leman algorithm distinguishes all non-isomorphic vertex-colored 2-connected graphs in 𝒢.
	Let G, G' ∈𝒢 be connected graphs that are not 2-connected with vertex colorings λ, λ', respectively. If for vertices v_1,v_2 ∈ V(G_⊥) and v'_1,v'_2∈ V(G'_⊥) we have χ^k_G_⊥(v_1,v_2) ≠χ^k_G'_⊥(v'_1,v'_2), then χ^k_G(v_1,v_2) ≠χ^k_G'(v'_1,v'_2).


By Lemma <ref>, with respect to the colorings χ^k_G and χ^k_G', the vertices in V(G_)  and V(G'_) have different colors than the vertices in V(G) ∖ V(G_) and V(G') ∖ V(G'_). Thus, it suffices to show that the colorings χ^k_G and χ^k_G' refine the colorings λ_ and λ'_, respectively. For this, by the definition of λ_ and λ'_, it suffices to show the following two statements.


  
  * If we have that v_1=v_2 and v'_1=v'_2 and also ((G^{v_1}_⊤,λ^{v_1}_⊤)_(v_1)) ≠((G'^{v'_1}_⊤,λ'^{v'_1}_⊤)_(v'_1)), then χ^k_G(v_1) ≠χ^k_G'(v'_1). 
  
  * If we have {v_1,v_2}∈ E(G) and {v'_1,v'_2}∈ E(G') and also λ_(v_1,v_2) ≠λ'_(v'_1,v'_2), then χ^k_G(v_1,v_2) ≠χ^k_G'(v'_1,v'_2).


For the first item, from ((G^{v_1}_⊤,λ^{v_1}_⊤)_(v_1)) ≠((G'^{v'_1}_⊤,λ'^{v'_1}_⊤)_(v'_1)) we know that v_1 and v'_1 must be cut vertices. Thus, the statement is exactly Lemma <ref>. For the second item, from the definition of λ_ and λ'_ we obtain λ(v_1,v_2) ≠λ'(v'_1,v'_2), which implies χ^k_G(v_1,v_2) ≠χ^k_G'(v'_1,v'_2). 



 Let (G, λ) and (G', λ') be vertex-colored graphs in 𝒞.
We prove the statement by induction on |V(G)|+|V(G')|. If both graphs are 2-connected, then the statement follows directly from the assumptions. If exactly one of the graphs is 2-connected, then exactly one of the graphs has a cut vertex and the statement follows from Lemma <ref>.
Thus suppose both graphs are not 2-connected but connected.
Since (G, λ) ≇(G', λ'), we know by Lemma <ref> that (G_, λ_) ≇(G'_,λ'_).
By Lemma <ref> the vertices in V(G_)  and V(G'_) have different colors than the vertices in V(G) ∖ V(G_) and V(G') ∖ V(G'_).
Moreover by Corollary <ref>, the partition of the vertices and arcs induced by the coloring χ^k_G restricted to V(G_) is finer than the partition induced by λ_. Similarly, the partition induced by χ^k_G' on V(G'_)  is finer than the partition induced by λ'_. By induction, the k-dimensional WL-algorithm distinguishes (G_, λ_) from (G'_,λ'_). Thus, the k-dimensional WL-algorithm distinguishes (G, λ) from (G', λ').
 







§ REDUCTION TO ARC-COLORED 3-CONNECTED GRAPHS


In this section our aim is to weaken the assumption from Theorem <ref> which requires that 2-connected graphs are distinguished to an assumption of 3-connected graphs being distinguished.

The strategy to prove our reduction follows similar ideas as those used in Section <ref>. It relies on the assumption that the input consists of vertex-colored 2-connected graphs, which we can make without loss of generality by the reduction from the last section. Now we consider the decomposition of vertex-colored 2-connected graphs into their so-called “3-connected components”. 

Most of the results stated in Section <ref> have analogous formulations for the 3- or higher-dimensional WL-algorithm on 2-connected graphs. But a 3-connected component of a 2-connected graph G is not necessarily a subgraph and may only be a minor of G. Thus, we require that the graph class 𝒢 is minor-closed. Furthermore, to enable the inductive approach we will now have to consider graphs G in which the 2-tuples (u,v) with {u,v}∈ E(G), i.e., the arcs, are also colored. However, it turns out that it is not sufficient to require that arc-colored graphs are distinguished. In fact we need the following stronger property.


 Let ℋ be a set of graphs. We say that the k-dimensional WL-algorithm correctly determines orbits in ℋ if for all arc-colored graphs (G, λ), (G',λ') with G, G' ∈ℋ and all vertices s ∈ V(G) and s' ∈ V(G') the following holds: there exists an isomorphism from (G,λ) to (G',λ') mapping s to s' if and only if χ^k_G(s) = χ^k_G'(s').

Note that for G' = G, the vertex color classes obtained by an application of the k-dimensional WL-algorithm to an arc-colored graph (G, λ) are the orbits of the automorphism group of G with respect to λ.


The main result in this section is the following reduction theorem.


 Let 𝒢 be a minor-closed graph class and assume k ≥ 3. Suppose the k-dimensional Weisfeiler-Leman algorithm correctly determines orbits on all arc-colored 3-connected graphs in 𝒢. Then the k-dimensional Weisfeiler-Leman algorithm distinguishes all non-isomorphic graphs in 𝒢.


The next corollary states that the 3-dimensional WL-algorithm distinguishes 2-separators from other pairs of vertices.


 Assume k ≥ 3 and let G and H be 2-connected graphs. Let u,v,u',v' be vertices such that G - {u,v} is disconnected and H - {u',v'} is connected. Then χ^k_G(u,v) ≠χ^k_H(u',v'). 



Consider the connected graphs G-{u} and H-{u'}. In the first graph v is a cut vertex but in the second graph v' is not a cut vertex. Thus, by Corollary <ref>, we have that χ^k-1_G-{u}(v) ≠χ^k-1_H-{u'}(v') and thus χ^k_G(u,v) ≠χ^k_H(u',v'). 



Just as we did in the previous section, we want to apply a recursive strategy that relies on Lemma <ref>.
However, to apply that lemma we require a minimum degree of 3. The following lemma states that vertices of degree 2 can be removed.


 Let 𝒢 be a minor-closed graph class and assume k ≥ 2. Suppose the k-dimensional Weisfeiler-Leman algorithm correctly determines orbits on all arc-colored graphs in 𝒢 of minimum degree at least 3. Then the k-dimensional Weisfeiler-Leman algorithm distinguishes all non-isomorphic arc-colored graphs in 𝒢.


 The proof is a basic exercise regarding the WL-algorithm. We give a sketch. By Theorem <ref> we can assume that the graphs are 2-connected.
We first observe that the 2-dimensional WL-algorithm identifies graphs of maximum degree at most 2. Since vertices of degree at least 3 obtain different colors than vertices of degree at most 2 it suffices now to observe that for each i the color χ^k_G(u,v) implicitly encodes the number of paths of length exactly i from u to v whose inner vertices are of degree 2. 
Inductively we can then consider the minors obtained by retaining vertices of degree at least 3 and connecting two such vertices with an edge if there is a path between them whose inner vertices all have degree 2. The edge is colored with a color that encodes the multiset of lengths of paths between the two vertices only having inner vertices of degree 2.


The lemma allows us to focus on graphs with minimum degree 3. Doing so, in analogy to Lemma <ref>, the following proposition gives a characterization of the vertices in V(G_⊥).


Assume k ≥ 3, let G be a 2-connected graph of minimum degree at least 3 that is not 3-connected. 
Then x ∉ V(G_⊥) if and only if there exists a vertex u contained in some minimal separator of G such that x∉ V((G-{u})_⊥) and such that the (unique) 2-connected component containing x in G-{u} has exactly one vertex belonging to a minimal separator of G.



If x∉ V(G_⊥) then x∈ K for a ({u,s},K) ∈ P_0(G). Then (s,K) ∈ P_0(G-{u}). Moreover, by Part <ref> of Lemma <ref>, no vertex of K is contained in a minimum separator of G. This implies that s is the only vertex in the 2-connected component of x in G-{u} that belongs to a minimum separator of G.

Conversely suppose u is a vertex in a minimal separator of G such that x∉ V((G-{u})_⊥) and the 2-connected component of x in G-{u} has exactly one vertex belonging to a minimal separator of G.
Since x∉ V((G-{u})_⊥), there is (s,K)∈ P_0(G-{u}) with x∈ K. Then K∪{s} is a 2-connected component of G-{u} and, since s is the only 
vertex in this 2-connected component that is contained in a minimal separator of G,
by Part <ref> of Lemma <ref>, we have ({u,s},K) ∈ P_0(G).




Assume k ≥ 3, let G, H be 2-connected graphs of minimum degree at least 3 that are not 3-connected. 
Then for vertices v ∈ V(G_⊥) and w ∈ V(H) ∖ V(H_⊥) we have χ^k_G(v) ≠χ^k_H(w).


 
Suppose that v ∈ V(G_⊥) and w ∈ V(H) ∖ V(H_⊥). Let u be a vertex contained in some minimal separator of H such that w∉ V((H-{u})_⊥) and such that the 2-connected component of w in H-{u} has exactly one vertex that is contained in a minimal separator of H. Such a vertex exists by Proposition <ref>. We argue that χ^k_G(v,t)≠χ^k_H(w,u) for all t∈ V(G). 

If t is not contained in any minimal separator, then this follows from Corollary <ref>. Otherwise we know that v∈ V((G-{t})_⊥) or the 2-connected component of v in G-{t} does not have exactly one vertex that is contained in a minimal separator of G.
In the first case we use Lemma <ref> and in the second case we use Theorem <ref> and Corollary <ref> to conclude that χ^k-1_G-{t}(v)≠χ^k-1_H-{u}(w) and thus χ^k_G(v,t)≠χ^k_H(w,u).





For k ≥ 3 suppose the k-dimensional Weisfeiler-Leman algorithm correctly determines orbits on all arc-colored 3-connected graphs in 𝒢. Suppose G, G' ∈𝒢 are arc-colored 2-connected graphs of minimum degree at least 3. Assume that ({s_1,s_2},K) ∈ P_0(G) and ({s'_1, s'_2},K') ∈ P_0(G'). 


If no isomorphism from (G_⊤^({s_1, s_2},K), λ_⊤^({s_1, s_2},K)) to (G_⊤'^({s'_1, s'_2},K'),λ_⊤'^({s'_1, s'_2},K')) maps s_1 to s'_1 and s_2 to s'_2, then

    {χ^k_G(s_1,s_2,v) | v ∈ K}∩{χ^k_G'(s'_1,s'_2,v) | v ∈ K'} = ∅.




This is an adaption of the proof of Lemma <ref>.

If χ^k_G(s_1,s_2) ≠χ^k_G'(s'_1,s'_2) then the conclusion of the lemma is obvious. Thus, we can assume otherwise. We have already seen with Corollary <ref> that 2-separators obtain different colors than other pairs of vertices. Thus, we can assume that G and G' are already colored in a way such that (s_1, s_2), (s_2, s_1), (s'_1, s'_2), (s'_2, s'_1) have colors different from the colors of pairs of vertices (t_1,t_2) with {t_1, t_2}∩ (K ∪ K') ≠∅. This immediately implies that we can assume that s_1, s_2, s'_1, s'_2 have colors different from colors of vertices that are not contained in any 2-separator in the graphs.

We will now argue that for v ∈ K and v' ∈ K' we have χ^k_G(v) ≠χ^k_G'(v'), which implies the lemma. For readability, we drop the superscripts ({s_1, s_2},K) and ({s'_1, s'_2},K'). 

We will show by induction that if the lemma does not hold, then for all i ∈ℕ, all u,v,w ∈ K ∪{s_1, s_2} and all u',v',w' ∈ K' ∪{s'_1, s'_2} with {u,v,w}⊈{s_1,s_2} and {u',v',w'}⊈{s'_1,s'_2} the following implication holds: 

    iχ_G_⊤^k(u,v,w) ≠iχ_G'_⊤^k(u',v',w') ⇒iχ_G^k(u,v,w) ≠iχ_G'^k(u',v',w').


For the induction base with i = 0, suppose 0χ_G_⊤^k(u,v,w) ≠0χ_G'_⊤^k(u',v',w'). Then either there is no isomorphism from G_⊤[u,v] to G'_⊤[u',v'] mapping u to u' and v to v', or λ_⊤(u,v,w) ≠λ'_⊤(u',v',w'). 

In the first case, by definition of the graphs G_⊤ and G'_⊤ and their colorings, we immediately get 0χ_G^k(u,v,w) ≠0χ_G'^k(u',v',w') since an isomorphism from G to G' that maps u to u' and v to v' would induce an isomorphism from G_⊤ to G'_⊤ with the same mappings. In the second case, since G and G' are arc-colored graphs, we have λ_⊤(u,v,w) = λ_⊤(u,v)  ≠λ'_⊤(u',v') = λ'_⊤(u',v',w'). If λ(u,v)  ≠λ'(u',v') then 0χ_G^k(u,v,w) ≠0χ_G'^k(u',v',w'). Otherwise, from the definitions of λ_⊤ and λ'_⊤ we conclude that (u,v)∈ E(G) ⇎ (u',v')∈ E(G') or
{u,v}⊆{s_1, s_2}⇎{u',v'}⊆{s'_1, s'_2}. In the first subcase, we conclude that 0χ_G^k(u,v,w) ≠0χ_G'^k(u',v',w'). In the second subcase, since ({s_1,s_2},K) ∈ P_0(G) and ({s'_1,s'_2},K') ∈ P_0(G') we know with Part <ref> from Lemma <ref> that either at least one of u and v or at least one of u' and v' is a vertex not contained in any 2-separator. Since we have assumed that s_1, s_2, s'_1, s'_2 have colors that are different from colors of vertices not contained in any 2-separator, we also conclude that 0χ_G^k(u,v,w) ≠0χ_G'^k(u',v',w'). 

For the induction step, assume that there exist vertices x,y,z ∈ K ∪{s_1,s_2} and vertices x',y',z' ∈ K' ∪{s'_1, s'_2} such that {x,y,z}⊈{s_1, s_2} and {x',y',z'}⊈{s'_1, s'_2}  with iχ_G_⊤^k(x,y,z) = iχ_G'_⊤^k(x',y',z') and i+1χ_G_⊤^k(x,y,z) ≠i+1χ_G'_⊤^k(x',y',z'). 

Thus, there must be a color triple (c_1,c_2,c_3) such that the sets

    M    {w | w ∈ V(G_⊤) \{x,y,z},
    
       {w | (iχ^k_G_⊤(w,y,z), 
    iχ^k_G_⊤(x,w,z), iχ^k_G_⊤(x,y,w)) = (c_1,c_2,c_3)}
    and
    M'    {w' | w' ∈ V(G'_⊤) \{x',y',z'}, 
       {w' | (iχ^k_G'_⊤(w',y',z'), iχ^k_G'_⊤(x',w',z'), iχ^k_G'_⊤(x',y',w')) = (c_1,c_2,c_3)}
    do not have the same cardinality. Let
    D    {(iχ^k_G(w,y,z), iχ^k_G(x,w,z), iχ^k_G(x,y,w)) | w ∈ M} ∪
       {(iχ^k_G'(w',y',z'), iχ^k_G'(x',w',z'), iχ^k_G'(x',y',w')) | w' ∈ M'}.

By induction and by Theorem <ref> we have that

    {w | w ∈ V(G) \{x,y,z}, (iχ^k_G(w,y,z), iχ^k_G(x,w,z),iχ^k_G(x,y,w)) ∈ D}   = M
    and{w' | w' ∈ V(G') \{x',y',z'}, (iχ^k_G'(w',y',z'), iχ^k_G'(x',w',z'),iχ^k_G'(x',y',w')) ∈ D}   = M'.

Hence these sets do not have the same cardinality. Thus, i+1χ_G^k(x,y,z) ≠i+1χ_G'^k(x',y',z'). 

Having shown Implication (<ref>), it suffices to show that 

    {χ^k_G_⊤(s_1,s_2,v) | v ∈ K}∩{χ^k_G'_⊤(s'_1,s'_2,v') | v' ∈ K'} = ∅.

For this, it suffices to prove that χ^k_G_⊤(s_1) ≠χ^k_G'_⊤(s'_1) holds. 

The graphs (G_⊤^({s_1,s_2},K), λ_⊤^({s_1,s_2},K)) and (G_⊤'^({s'_1,s'_2},K'), λ_⊤'^({s'_1,s'_2},K')) are 3-connected. Thus, if we had that χ^k_G_⊤(s_1) = χ^k_G'_⊤(s'_1), there would have to be an isomorphism from the graph (G_⊤^({s_1, s_2},K), λ_⊤^({s_1, s_2},K)) to (G_⊤'^({s'_1, s'_2}',K'),λ_⊤'^({s'_1, s'_2},K')) that maps s_1 to s'_1 since we have assumed that the k-dimensional WL-algorithm correctly determines orbits on all arc-colored 3-connected graphs in 𝒢. However, by definition of λ_⊤^({s_1, s_2},K) and λ_⊤'^({s'_1, s'_2},K'), this isomorphism would also map s_2 to s'_2 contradicting the assumptions of the lemma.


Using the lemma, we can show the following.


Assume k ≥ 3 and suppose the k-dimensional Weisfeiler-Leman algorithm correctly determines orbits on all arc-colored 3-connected graphs in 𝒢. Assume G, G' ∈𝒢 are arc-colored 2-connected graphs of minimum degree at least 3 and let {s_1,s_2}⊆ V(G) and {s'_1, s'_2 }⊆ V(G') be 2-separators of G and G', respectively. 

If no isomorphism from (G_⊤^{s_1, s_2}, λ_⊤^{s_1, s_2}) to (G_⊤'^{s'_1, s'_2},λ_⊤'^{s'_1, s'_2}) maps s_1 to s'_1 and s_2 to s'_2, then χ^k_G(s_1,s_2) ≠χ^k_G'(s'_1,s'_2). 


 
This proof is similar to the proof of Lemma <ref>. Suppose that

    {K_1,…,K_t}    = {K | ({s_1,s_2},K) ∈ P_0(G)}and that{K'_1,…,K'_t'}    = {K' | ({s'_1,s'_2},K') ∈ P_0(G')}.

Since there is no isomorphism from (G_⊤^{s_1, s_2}, λ_⊤^{s_1, s_2}) to (G_⊤'^{s'_1, s'_2}, λ_⊤'^{s'_1, s'_2}) that maps s_1 to s'_1 and s_2 to s'_2, there is an arc-colored graph (H,λ_H) such that the sets

    I    {j|(G_⊤^({s_1,s_2},K_j), λ_⊤^({s_1,s_2},K_j))_(s_1,s_2)≅ (H,λ_H)}and
    I'    {j|(G'_⊤^({s'_1,s'_2},K'_j), λ_⊤'^({s'_1,s'_2},K'_j))_(s'_1,s'_2)≅ (H,λ_H)}

have different cardinalities. Note that all K_j with j∈ I and all K'_j with j∈ I' have the same cardinality. We know by Lemma <ref> that for v∈ K_i with i∈ I and v'∈ K_j with j∉ I' we have χ^k_G(s_1,s_2,v)≠χ^k_G'(s'_1,s'_2,v'). Letting C {χ^k_G(s_1,s_2,v)| i∈ I  and  v∈ K_i}, the sets {v|χ^k_G(s_1,s_2,v)∈ C} and {v'|χ^k_G'(s'_1,s'_2,v')∈ C} do not have the same cardinality. We conclude that χ^k_G(s_1,s_2) ≠χ^k_G'(s'_1,s'_2).



	Assume k ≥ 3 and suppose the k-dimensional Weisfeiler-Leman algorithm correctly determines orbits on all arc-colored 3-connected graphs in 𝒢. Let G, G' ∈𝒢 be arc-colored 2-connected graphs of minimum degree at least 3. If for vertices v_1,v_2 ∈ V(G_⊥) and v'_1,v'_2∈ V(G'_⊥) we have χ^k_G_⊥(v_1,v_2) ≠χ^k_G'_⊥(v'_1,v'_2), then χ^k_G(v_1,v_2) ≠χ^k_G'(v'_1,v'_2).


By Lemma <ref>, with respect to the colorings χ_G^k and χ_G'^k, the vertices in V(G_) and V(G'_) have different colors than the vertices in V(G) ∖ V(G_) and V(G') ∖ V(G'_). Thus, it suffices to show that the colorings χ^k_G and χ^k_G' refine the colorings λ_ and λ'_, respectively. For this, by the definition of λ_ and λ'_, it suffices to show the following two statements.


  
  * If {v_1,v_2} and {v'_1,v'_2} are 2-separators and ((G^{v_1,v_2}_⊤,λ^{v_1,v_2}_⊤)_(v_1,v_2)) ≠((G'^{v'_1,v'_2}_⊤,λ'^{v'_1,v'_2}_⊤)_(v'_1,v'_2)), then χ^k_G(v_1,v_2) ≠χ^k_G'(v'_1,v'_2). 
  
  * If v_1=v_2 and v'_1=v'_2, or {v_1,v_2}∈ E(G) and {v'_1,v'_2}∈ E(G') but {v_1,v_2} and {v'_1,v'_2} are not 2-separators, if λ_(v_1,v_2) ≠λ'_(v'_1,v'_2), then χ^k_G(v_1,v_2) ≠χ^k_G'(v'_1,v'_2).


The first item is exactly Lemma <ref>. For the second item, from the definition of λ_ and λ'_ we obtain λ(v_1,v_2) ≠λ'(v'_1,v'_2), which implies χ^k_G(v_1,v_2) ≠χ^k_G'(v'_1,v'_2). 



 
By Theorem <ref> it suffices to show the statement for vertex-colored 2-connected graphs. To allow induction we will show the statement for arc-colored 2-connected graphs. Let (G, λ) and (G', λ') be arc-colored 2-connected graphs in 𝒢.
We prove the statement by induction on |V(G)|+|V(G')|. If both graphs are 3-connected then the statement follows directly from the assumptions. If exactly one of the graphs is 3-connected, then exactly one of the graphs has a 2-separator and the statement follows from Corollary <ref>.

Thus suppose both graphs are not 3-connected. By Lemma <ref> we can assume that both graphs have minimum degree at least 3.
Since (G, λ) and (G', λ') are not isomorphic, we know by Lemma <ref> that (G_, λ_) ≇(G'_,λ'_). Note that G_ and G'_ are 2-connected.
By Lemma <ref> the vertices in V(G_)  and V(G'_) have different colors than the vertices in V(G) ∖ V(G_) and V(G') ∖ V(G'_).
Moreover by Corollary <ref>, the partition of the vertices and arcs induced by the coloring χ^k_G restricted to V(G_)  is finer than the partition induced by λ_. Similarly, the partition induced by χ^k_G' on V(G'_)  is finer than the partition induced by λ'_. By induction the k-dimensional WL-algorithm distinguishes (G_, λ_) from (G'_,λ'_). Thus the k-dimensional WL-algorithm distinguishes (G, λ) from (G', λ').
 

In the last two sections we have concerned ourselves with graphs being distinguished (referring to two input graphs from a class) rather than graphs being identified (referring to one input graph from a class and another input graph being arbitrary). However, the theorems we prove also have 
corresponding versions concerning the latter notion.

For a graph G the Weisfeiler-Leman dimension of G is the least integer k such that the k-dimensional WL-algorithm distinguishes G from every non-isomorphic graph G'.


Let 𝒢  be a minor-closed graph class. The Weisfeiler-Leman dimension of graphs in 𝒢 is at most max{3,k}, where k is the minimal number ℓ such that the ℓ-dimensional Weisfeiler-Leman algorithm correctly determines orbits on all arc-colored 3-connected graphs in 𝒢 and identifies such graphs.


The proof follows almost verbatim the lines of the entire proof of Theorem <ref> outlined in the last two sections replacing “distinguishes” with “identifies”. 





§ ARC-COLORED 3-CONNECTED PLANAR GRAPHS


Let G be a 3-connected planar graph. We show that typically we can individualize two vertices in G so that applying the 1-dimensional WL-algorithm yields a discrete graph. There are some 3-connected planar graphs for which this is not the case. However, we can precisely determine the collection of such exceptions. 


We call a graph G an exception if G is a 3-connected planar graph in which there are no two vertices v,w in G such that χ^1_G_(v,w) is the discrete coloring.


Here and in the following we denote by G_(v_1,v_2,…,v_t) the colored graph obtained from the (uncolored) graph G by individualizing the vertices v_1,v_2,…,v_t in that order. More specifically, we let G_(v_1,v_2,…,v_t) be the colored graph (G,λ) with

    λ(v) i    if v=v_i
     0    if v∉{v_1,…,v_t}.

As before χ^1_H denotes the stable coloring of the 1-dimensional WL-algorithm applied to the graph H.
 


Let G be a 3-connected planar graph and let v_1,v_2,v_3 be vertices of G. If v_1,v_2,v_3 lie on a common face, then χ^1_G_(v_1,v_2,v_3) is a discrete coloring.



We will use the Spring Embedding Theorem of Tutte <cit.> (see <cit.>) which is as follows. Let v_1,v_2,v_3 be vertices of a common face of G.
Let μ_0  V(G)∖{v_1,v_2,v_3}→ℝ^2 be an arbitrary mapping that satisfies μ_0(v_1) = (0,0), μ_0(v_2) = (1,0) and μ_0(v_3) = (0,1). 
For i∈ℕ we define μ_i+1 recursively by setting

    μ_i+1(v) = 1/d(v)∑_w∈ N(v)μ_i(w)    if v∉{v_1,v_2,v_3},
    μ_i(v)    otherwise.
 
Then Tutte's result says that this recursion converges to a barycentric planar embedding of G, that is, an embedding in which every vertex not in {v_1,v_2,v_3} is contained in the convex hull of its neighbors <cit.>. 
This implies that after a finite number of steps the barycentric embedding is injective, i.e., no two vertices are mapped to the same image.

From the theorem, we will only require the fact that for some i the map μ_i is injective.
Choose μ_0 with the requirements above and so that all vertices in V(G)∖{v_1,v_2,v_3} have the same image. For example set μ_0(v) = (1,1) for v∈ V(G)∖{v_1,v_2,v_3}.

We argue the following statement by induction on i.
For every two vertices v and v', it holds that

    μ_i(v)≠μ_i(v')   ⇒  iχ^1_G_(v_1,v_2,v_3)(v)≠iχ^1_G_(v_1,v_2,v_3)(v'),

where iχ^1_G_(v_1,v_2,v_3)(x) denotes the color of vertex x after the i-th iteration when the 1-dimensional WL algorithm is applied to G_(v_1,v_2,v_3).  

For i=0 the statement holds by the definition of μ_0 and the fact that v_1, v_2 and v_3 are singletons in G_(v_1,v_2,v_3).
For i>0, if ∑_w∈ N(v)μ_i(w)  ≠∑_w'∈ N(v')μ_i(w') then the multisets {{μ_i(w) | w ∈ N(v) }} and {{μ_i(w') | w' ∈ N(v')}} are different and thus, by induction, the multisets {{iχ^1_G_(v_1,v_2,v_3)(w) | w ∈ N(v) }} and {{iχ^1_G_(v_1,v_2,v_3)(w') | w' ∈ N(v')}} are different.

We conclude with the fact that for some i the map μ_i is injective implying that iχ^1_G_(v_1,v_2,v_3) and therefore also χ^1_G_(v_1,v_2,v_3) are discrete colorings.


From the lemma one can directly conclude that for k≥ 4, the k-dimensional WL-algorithm correctly determines the orbits of every 3-connected planar graph.



For k≥ 4, the k-dimensional Weisfeiler-Leman algorithm  correctly determines orbits of arc-colored 3-connected planar graphs.



Let G be an arc-colored 3-connected planar graph. Then by Lemma <ref>, there are vertices v_1, v_2, v_3 such that χ^1_G_(v_1,v_2,v_3) is discrete (the additional arc coloring can only refine the stable coloring of the uncolored graph). This implies that the multiset C {{χ^4_G(v_1,v_2,v_3,x)| x∈ V(G) }} contains n different colors. Let H be a second arc-colored 3-connected planar graph. If H contains vertices v_1',v_2',v_3' such that we have {{χ^4_H(v'_1,v'_2,v'_3,x')| x'∈ V(H) }} = C, then G and H are isomorphic via an isomorphism that maps v_1 to v'_1. Otherwise the color χ^4_G(v_1,v_2,v_3,v_3) is for all v'_1,v'_2,v'_3∈ V(H) different from the color χ^4_H(v'_1,v'_2,v'_3,v'_3) implying that G and H are distinguished and thus their sets of vertex colors are disjoint.


This is also true for k=3. The proof amounts to proving the following theorem. 


If G is an exception (i.e., G is a 3-connected planar graph without a pair of vertices v,w such that χ^1_G_(v,w) is discrete), then G is isomorphic to one of the graphs in Figure <ref>.


Before we present the lengthy proof of the theorem, we state its implications.


Let G be a 3-connected planar graph. The fixing number of G is at most 3 with equality attained if and only G is isomorphic to an exception (i.e., a graph depicted in Figure <ref>).



If in a given graph there is a set of ℓ vertices such that individualizing all vertices in the set and then applying the 1-dimensional WL-algorithm yields a discrete coloring, then Theorem <ref>, a graph that is not an exception has fixing number at most 2. To conclude the corollary it thus suffices to check that all exceptions have fixing number 3.  




For k≥ 3, the k-dimensional Weisfeiler-Leman algorithm correctly determines orbits of arc-colored 3-connected planar graphs.



Suppose G is an arc-colored 3-connected planar graph that is not an exception. Then there are vertices v and w such that χ^1_G_(v,w) is discrete. Analogously to the proof of Corollary <ref>, we obtain that for any second arc-colored 3-connected planar graph H, the 3-dimensional WL-algorithm only assigns equal colors to a vertex of G and a vertex of H if there is an isomorphism mapping the one to the other. 

With direct computations, one can check that each arc-colored exception is distinguished from all arc-colored 3-connected planar graphs and that on each arc-colored exception the stable coloring under the 3-dimensional Weisfeiler-Leman algorithm induces the orbit partition on the vertices.


The task in the rest of this section is to show Theorem <ref>. The proof of the theorem is a lot more involved than the proof of Corollary <ref>. Thus, at the expense of increasing k by 1 from 3 to 4 in the main theorem (Theorem <ref>), the reader may skip the following lengthy exposition. 

We determine the exceptions in a case-by-case analysis with respect to the existence of vertices of certain degrees. 
The following two lemmas serve as general tools to deduce information about the structure of these input graphs. 

For a subgraph G' of a graph G we say that v∈ G' is saturated in G' with respect to G if d_G'(v)= d_G(v). Thus, if a vertex is saturated, then its neighbors in G and in G' are the same.


Let G be a 3-connected planar graph.


  *  Let G' be a subgraph of G and suppose that the sequence v_1,…, v_t forms a face cycle in the planar embedding of G' induced by a planar embedding of G. If in {v_1,…,v_t} there are at most two vertices that are not saturated in G' with respect to G, then V(G) = {v_1,…,v_t} or v_1,…,v_t is a face cycle of G.

  *   If v_1,…,v_t is a 3-cycle or an induced 4-cycle of G that contains two vertices of degree 3 in G, then V(G) = {v_1,…,v_t} or v_1,…,v_t is a face cycle of G.




For Part <ref>, suppose v_1,…, v_t forms a face cycle of G' and there are at most two vertices v_i and v_j that are not saturated in G' with respect to G. 
Assume v_1,…, v_t is not a face cycle in G. Then the vertices v_i and v_j are the only ones among v_1,…,v_t that have neighbors in G inside the region of the plane corresponding to the face cycle of G' formed by v_1,…,v_t. Therefore, if  V(G)≠{v_1,...,v_t}, then {v_i,v_j} is a separator of G, which contradicts the 3-connectivity.

For Part <ref> consider an induced 4-cycle v_1,…,v_4 which contains two vertices v_i and v_j that have degree 3 in G. If v_1,…,v_4 is not a face cycle of G, then {v_1,…,v_4}∖{v_i,v_j} is a separator of size 2.
The argument for a 3-cycle v_1,…,v_3 is similar.



Let G be an exception and let v be a vertex of G. Let u_1, …, u_d(v) be the cyclic ordering of the neighbors of v induced by a planar embedding of G. Then every pair of vertices u_i, u_i+1 has a common neighbor of degree d(v) other than v.



If u_i and u_i+1 do not have a common neighbor of degree d(v) other than v, the coloring χ^1_G_(u_i,u_i+1) has the three singletons u_i, v, u_i+1, which lie on a common face. Thus, by Lemma <ref>, the coloring χ^1_G_(u_i,u_i+1) is discrete, contradicting the assumption that G is an exception.


Now we can start determining the structure of the exceptions.


If G is an exception that has a vertex of degree 5, then it is isomorphic to the icosahedron or the bipyramid on 7 vertices.



To simplify notation, we let χ_G χ^1_G in the course of this proof. 
Let G be an exception with a vertex v of degree 5. Let N  N(v) be the set of neighbors of v and let (u_1,…,u_5) be their circular ordering. For convenience we will take indices modulo 5. 

By Lemma <ref>, every pair u_i,u_i+1 has a common neighbor x_i,i+1 of degree 5 other than v. (We remark that the vertices x_i,i+1 are not necessarily distinct or unique.)

For all i∈{1,…,5}, every pair of vertices u_i,u_i+2 has a common neighbor x_i,i+2 of degree 5 other than v. 

To show the claim assume without loss of generality that u_1 and u_3 do not have a common neighbor of degree 5 other than v. Consider the coloring χ_G_(u_1,u_3).
In this coloring the vertex v is a singleton.  It follows that N is the union of three color classes of the coloring χ_G_(u_1,u_3), one of which is {u_2, u_4, u_5}. (Otherwise, there are two consecutive vertices in N that are singletons and thus χ_G_(u_1,u_3) is discrete by Lemma <ref>.)



[x_1,2∈ N or  x_2,3∈ N] 
We only consider the case that x_1,2∈ N, since the case x_2,3∈ N is analogous.  We know that u_2, u_4 and u_5 have the same degree in G[N] and thus the vertices u_1 and u_3 must have the same degree in G[N] since otherwise one of them would have a unique degree in G[N] (and then some u_i would be a singleton in χ_G_(v) and thus χ_G_(v,u_i+1) would be discrete by Lemma <ref>).

Now suppose first x_1,2 = u_4 or x_1,2 = u_5. Either way, one vertex and thus all the vertices u_2,u_4,u_5 are adjacent to u_1, since they form a color class of χ_G_(u_1,u_3). It follows that the degree of u_1 and hence of u_3 in G[N] is at least 3. Thus, u_1 and u_3 have a common neighbor. It has degree 5 since x_1,2 has degree 5. The case x_1,2 = u_3 can be treated analogously by simply swapping the roles of u_1 and u_3. 

[x_1,2∉ N and x_2,3∉ N]
Since u_2 and u_4 have the same color, the vertices u_1 and u_4 have a common neighbor x∉ N of degree 5 other than v. Similarly u_3 and u_5 have a common neighbor x'∉ N of degree 5 other than v. By the planarity of G, we have x= x', and thus x is a vertex of degree 5 adjacent to u_1 and to u_3.





Having proved the claim we now finish the proof of Lemma <ref>.
Again we distinguish cases.


[G[N] is non-empty and some vertex in N has degree 5 in G]

Due to plana­rity there can be at most one vertex in N that has degree 4 within G[N]. Indeed, if there were two such vertices u_i and u_j, then each of v, u_i, u_j would be adjacent to all vertices in N \{u_i, u_j}, yielding a K_3,3 minor. However, no vertex in N can have a unique degree in G[N] and thus G[N] has a maximum degree of at most 3. Suppose that G[N] contains an edge {u_i,u_i+2} for some i, say i=1. Due to Claim <ref>, the vertex u_2 must share a common neighbor with each of u_4 and u_5 apart from v. By planarity these common neighbors are in {u_1,u_3}. However the two common neighbors must be different since otherwise the respective vertex has degree 4 in G[N]. Thus u_2 is adjacent to u_1 and u_3 and both u_1 and u_3 have degree 3 in G[N]. 

By the planarity of G, the vertex u_2 has degree 2 in G[N]. Suppose u_4 has degree 3 in G[N]. Then it must be adjacent to u_1, u_3 and u_4. Since u_5 cannot have a unique degree in G[N], it must be adjacent to u_3, i.e., it must have degree 2 in G[N]. (By planarity, it cannot be adjacent to u_1.) However, this would give u_3 a degree of 4 in G[N], yielding a contradiction. The case that u_5 has degree 3 in G[N] is symmetric. Thus, u_1 and u_3 are the only vertices of degree 3 in G[N].

Then u_2 is the only vertex of N that is adjacent to two vertices of degree 3 in G[N], making u_2 a singleton in χ_G_(v) and yielding a contradiction.

We conclude that there is no edge of the form {u_i,u_i+2}. This implies that in G[N] there is no vertex of degree 1. (Otherwise, we could individualize this vertex and v, and together with their unique common neighbor, they would yield a discrete coloring by Lemma <ref>.)  Consequently, since G[N] is non-empty, we conclude that u_1,u_2,…,u_5 is an induced cycle in G[N]. Since some vertex in N has degree 5 and within G[N] the two neighbors of each vertex must have the same degree, we conclude that all vertices in N have degree 5.

Thus, if a vertex fulfills Case <ref>, then all its neighbors also fulfill Case <ref>. Therefore, being connected, the entire graph G must be a 5-regular triangulated planar graph since we have restricted ourselves to connected graphs.
Being 5-regular, the graph has m= 5/2 n edges, and being a triangulation the number of edges is m=3n-6. We conclude that n=12.
There is only one 5-regular graph on 12 vertices, the icosahedron (see for example <cit.>).
 
[G[N] is empty or no vertex in N has degree 5 in G] 

From Claim <ref> we already know that every pair of vertices u_i, u_i+2 has a common neighbor of degree 5 other than v. In Case <ref> this vertex cannot be in N. Due to planarity, all these common neighbors for different i must be equal to a single vertex y adjacent to all vertices of N.

Observing that y has degree 5, consider the subgraph H  G[{v,y,u_1,…,u_5}] of G. With the described circular ordering of the vertices in N there is only one planar drawing of H up to equivalence. In this drawing every face is a 4-cycle or a 3-cycle containing y and v. Since y and v have degree 5 in G, but they already have degree 5 in H, they are saturated. 
Thus, since both y and v belong to each face of H, by Lemma <ref>, no interior of a face of the drawing of H contains vertices of G. Therefore G = H =  G[{v,y,u_1,…,u_5}]. Since G is 3-connected, G[N] cannot be empty. Similarly as in Case <ref> we conclude that u_1,u_2,…,u_5 is a cycle rendering G the bipyramid on 7 vertices.






If G is an exception that has a vertex of degree 3, then it is isomorphic to a tetrahedron, a cube, a triangular bipyramid, a triakis tetrahedron, a rhombic dodecahedron, or a triakis octahedron.



Assume G is a 3-connected planar graph with a vertex of degree 3 and that G does not have two vertices, individualization of which followed by an application of the 1-dimensional WL-algorithm produces the discrete partition.
 
Let v be a vertex of degree 3 in G and
let N N(v)= {u_1,u_2,u_3} be its neighbors. 
By Lemma <ref>, no vertex of N can have a unique degree in G. Thus, the graph G[N] is either a triangle or empty.

By Lemma <ref>, for i∈{1,2,3} (indices always taken modulo 3) the pair u_i,u_i+1  has a common neighbor x_i,i+1 of degree 3 other than v. (As in the previous proof, these x_i,i+1 are not necessarily distinct or unique.) If x_i,i+1∈ N then x_i,i+1= u_i+2 and N({u_i+2,v}) = {u_i,u_i+1}. Thus, unless G only has 4 vertices (in which case it is the tetrahedron), the set {u_i,u_i+1} forms a 2-separator, which contradicts G being 3-connected. We can therefore assume for all i∈{1,2,3} that x_i,i+1∉ N.

We claim that v, u_i,x_i,i+1, u_i+1 is a face cycle of G, or u_i and u_i+1 are adjacent and both u_i,u_i+1,x_i,i+1 and u_i,u_i+1,v are face cycles. The vertex x_i,i+1 has degree 3, so the claim follows directly from Part <ref> of Lemma <ref>.


[G[N] is empty]

In this case every face incident to v is a 4-cycle consisting of two non-adjacent vertices of degree 3 in G and two other vertices of degree d≥ 3. By analogous arguments as for v, for every i ∈{1,2,3}, the graph G[N(x_i,i+1] must be either empty or a triangle. It cannot be a triangle because the edge {u_i,u_i+1} is not present. So by successively replacing v by its opposite vertices in the incident 4-cycles, we conclude that G is a (3,d)-bi-regular quadrangulation.  


[G is 3-regular] 
In this subcase G must be a 3-regular quadrangulation. Such a graph has m= 3n/2 edges, since it is 3-regular, but also m= 2n-4 edges since it is a quadrangulation.
Thus n = 8. It is easy to verify that the only 3-regular planar quadrangulation on 8 vertices is the cube.

[G is not 3-regular] 
Then G is bipartite and bi-regular with degrees 3 and d say. Let n_3 and n_d be the number of vertices of degree 3 and d, respectively. Then 3 n_3 = d n_d by double counting and d n_d = m = 2n-4 since G is a quadrangulation. It follows that d n_d = 2(n_3+n_d)-4 = 2(d n_d/3+n_d)-4 which gives that 4 = n_d (2-d/3). Thus d≤ 5. The case d=3 is Case <ref> and d=5 cannot occur according to Lemma <ref>.

We conclude that G is a (3,4)-biregular quadrangulation. We have 3n_3 = 4n_4. Then m = 3 n_3 = 3 · 4/7 n. But also m = 2n-4. Thus n= 14. If we modify G by adding an edge between every pair of degree 3 vertices that share a common face and by removing all vertices that originally had degree 4, we obtain a new graph G' that is a 3-regular planar quadrangulation on 8 vertices.  The only such graph is the cube. Undoing the modification we obtain that G is the rhombic dodecahedron.


[G[N] is a triangle]

In this case every face in G is a 3-cycle consisting of a vertex of degree 3 and two other vertices of equal degree d.


[G is 3-regular, i.e., d=3]
Then G is a 3-regular triangulation. Thus m = 3/2 n and m = 3n-6, thus n= 4. We conclude that G is the tetrahedron.

[G is not 3-regular]
Consider the graph G' obtained from G by removing all vertices of degree 3. The resulting graph is a planar d/2-regular triangulation. Indeed, since v was chosen arbitrarily among all vertices of degree 3 and the vertices x_i,i+1 have degree 3 as well, it is easy to see that the resulting graph is a triangulation. Moreover, one can verify that in G for every vertex of degree d, in the cyclic ordering of its neighbors, the degrees 3 and d alternate. Thus, a deletion of the vertices of degree 3 halves the degrees of each of the other vertices.

It follows that d/2∈{2,3,4,5}. For d/2 =2 we obtain a 3-cycle. This implies that G is a triangular bipyramid. For d/2=3 we conclude that G' is a tetrahedron. This implies that G is a triakis tetrahedron. For d/2=4 we obtain an octahedron. This implies that G is the triakis octahedron. For d/2=5 we would obtain an icosahedron. This would imply that G is the triakis icosahedron. However in this solid, there are two vertices u,u' (namely vertices of degree 3 of distance 2 that only have one common neighbor) such that χ^1_G_(u,u') is discrete.





If G is an exception that has a vertex of degree 4, then it is isomorphic to a bipyramid, a rhombic dodecahedron or a tetrakis hexahedron.



Assume G is an exception with a vertex of degree 4. First we make two observations that hold for every vertex u of degree 4 with neighbors v_1,v_2,v_3,v_4 in cyclic order.

Observation 1:  It holds that d(v_1)= d(v_3) and d(v_2)= d(v_4). Otherwise we can individualize u and a neighbor v_i of u so that v_i+1 or v_i-1 refines to a singleton class, which yields a contradiction. 

Observation 2:  By a similar argument, the induced graph G[v_1,v_2,v_3,v_4] either is empty or forms an induced cycle such that v_i is adjacent to v_i+1  for all i∈{1,2,3,4} (indices  taken modulo 4). 

Due to Observation [obs:2]2, if G is 4-regular then G is either a triangulation or every face is of size at least 4. In the first case G has n=6 vertices (since m= 4n/2 and m=3n-6), and thus G is the octahedron (a bipyramid).

The second case cannot occur since a planar graph without triangle faces has at most 2n-4 edges, but a 4-regular graph has 2n edges. 

We can thus assume that G has a vertex v of degree other than 4 that is adjacent to a vertex of degree 4.
By Lemmas <ref> and <ref> we can assume that G neither has a vertex of degree 5 nor a vertex of degree 3.
Thus, we can assume that v has degree at least 6. Let N  N(v) be the set of neighbors of v and let N_4⊆ N be those neighbors of v that are of degree 4. Suppose (u_1,…,u_t) is the cyclic order of N_4 induced by the cyclic order of N.


[G[N_4] is non-empty] 
First assume there are distinct u,u'∈  N_4 that are adjacent, i.e., G[N_4] is non-empty. According to Observation [obs:1]1, each vertex in N_4 must have two neighbors in G of degree d(v)≠ 4, and thus G[N_4] has maximum degree 2.
We argue that G[N_4] cannot have a vertex of degree 1. Indeed, if u_i were a vertex that has degree 1 in G[N_4] then u_i would have two neighbors of degree d(v) and two neighbors of degree 4, one of which adjacent to v and one of which non-adjacent to v. This means that in χ^1_G_(v,u_i) all neighbors of u_i are singletons, since the two neighbors of u_i of degree 4 disagree on being adjacent to v or not. This is impossible by Lemma <ref>. We conclude that G[N_4] has only vertices of degree 2 and 0. Since G[N_4] is non-empty, this implies that there is some cycle in G[N_4]. Assume this cycle has an edge {u_i,u_j} connecting two vertices that are not consecutive in the cyclic order (u_1,…,u_t). 

Let u_i^+ and u_i^- be the vertices of G[N] following and preceeding, respectively, the vertex u_i in the cyclic ordering of N (so they may or may not have degree 4). By Lemma <ref>, there must be vertices x^+ and x^- of degree d(v)≠ 4 such that x^+ is adjacent to both u_i and u_i^+ and x^- is adjacent to both u_i and u_i^-. However, x^+≠ x^- since the cycle v,u_i,u_j separates u_i^+ from u_i^-. We conclude that u_i has the following five neighbors: the vertex v, two neighbors in N_4 as well as x^+ and x^-. But u_i has degree 4, which gives a contradiction.
We conclude that u_i is adjacent to u_i+1 for all i∈{1,…,t}.

Finally, by Observation [obs:1]1, every pair of vertices {u_i, u_i+1} must have a common neighbor other than v of degree d(v) (otherwise all neighbors of u_i would be singletons in χ^1_G_(u_i,u_i+1)).

Since u_i is adjacent to v,u_i+1 and u_i-1, it can only have one further neighbor. Thus, all these common neighbors for the pairs {u_i, u_i+1} for i∈{1,… ,t} are indeed the same vertex x. Consider G'  G[{u_1,…,u_t,v,x}]. The graph G' is 3-connected and every face is a 3-cycle with two vertices saturated in G' with respect to G. Part <ref> of Lemma <ref> implies that G=G'. We conclude that G is isomorphic to a bipyramid.

[G[N_4] is empty]
In the second case we now assume that the degree 4 neighbors of v form an independent set.

For every i∈{1,…,t} there is a vertex x_i,i+1 such that either the sequence v,u_i,x_i,i+1,u_i+1 forms a face cycle or both v,u_i,x_i,i+1  and v,u_i+1,x_i,i+1 are face cycles.

Without loss of generality, we show the claim for i=2.
We first argue that there are vertices u'∈ N_4 and x' such that v,u_2,x',u' is a 4-cycle. For this
let x' be the first neighbor following v in the cyclic ordering among the neighbors of u_2. Then by Lemma <ref>, there must be a vertex u' other than u_2 of degree 4 that is adjacent to x' and v. Let u_j∈ N_4 be the first neighbor of v following u_2 in the cyclic ordering of vertices in N_4 that has a common neighbor with u_2 other than v.

 We choose a common neighbor x of u_2 and u_j so that it is closest to v: more precisely, for a common neighbor x≠ v of u_2 and u_j consider the cycle u_2,v,u_j,x. It bounds two areas, one of which contains the vertices of N that follow u_2 but precede u_j while the other one contains the vertices that follow u_j but precede u_2 in the cyclic order of N. (One of these sets may be empty.) We choose x so that the first of these areas is minimal with respect to inclusion and we call this area A.

We claim that the 4-cycle u_j, x,u_2, v is a face cycle of G or a face cycle after removing the diagonal {x,v} (i.e.,  the 3-cycles v,u_2,x and v,u_j,x are faces). (Note that the edge {u_2,u_j} cannot be present since G[N_4] is empty.) Indeed, suppose that u_2 has a neighbor that lies within A. Choose as such a neighbor z the vertex that precedes v in the cyclic ordering of neighbors of u_2. Then for some vertex u̅∈ N_4, the sequence (v,u_2,z, u̅) forms a 4-cycle (Lemma <ref> applied to χ^1_G_(v,z)). Now, either u̅ precedes u_j in the cyclic ordering of N_4 starting from u_2 or u̅= u_j, but {v,u_2,z, u_j} bounds an area that is a proper subset of A. Either case contradicts the minimal choices of u_j and x.
 
Finally assume that u_j has a neighbor z that lies within A. Choose z to be the vertex that follows v in the cyclic ordering of neighbors of u_j. Since {v,x} is not a separator and u_2 does not have a neighbor inside A, there must be a path from z to u_2 via u_j that leaves A. Thus, the vertex u_j must have some neighbor outside of A. Hence, since u_j has degree 4, the vertex z is the only neighbor of u_j inside A.

By Lemma <ref>, for some vertex u̅∈ N_4, the sequence (v,u_j,z, u̅) must be a 4-cycle. Consider the coloring χ^1_G_(u_2,u̅). In this coloring v is a singleton, since by the minimality of u_j it is the only common neighbor of u_2 and u̅. Furthermore, u_j is the only vertex in N_4 that has simultaneously a common neighbor with u_2 other than v and a common neighbor with u̅ other than v and thus u_j is a singleton. Moreover, u̅ and u_j only have one common neighbor other than v, namely z, which is then a singleton as well. The singletons v,u_j and z lie on a common face by the choice of z which yields a contradiction with Lemma <ref>. 

Thus, neither u_2 nor u_j have a neighbor inside the cycle. This implies that the cycle u_j, x,u_2, v is a face or it becomes a face after removing the possible diagonal {x,v}, since otherwise the set {x,v} would be a separator. We conclude that u_j=u_3 and that the vertex x_2,3 x justifies the claim. 


In the following we call an edge of G a diagonal if neither of its endpoints has degree 4.

Overall the claim implies that at least every second neighbor of v is of degree 4 (in particular |N|≤ 2|N_4|) and thus, being of degree at least 6, the vertex v has at least 3 neighbors of degree 4, i.e., |N_4|≥ 3.


Recall that u_1 and u_3 are the two vertices in N_4 that are closest to u_2 in the cyclic ordering of neighbors of degree 4 of v.

We distinguish several cases according to the size of N_4.


[|N_4| = 3]  

Since v must have degree at least 6 and at least every second of its neighbor has degree 4, we conclude that v also has exactly three neighbors of degree larger than 4.
Thus, the degree of v is 6. Let (u_1,t_1,u_2,t_2,u_3,t_3) be the neighbors of v in cyclic order. Then by Claim <ref>, the vertices u_i,t_i,v form a face cycle for every i∈{1,2,3}. Likewise t_i,u_i+1,v is a face cycle. Thus, the graph induced by N ∪{v} is a wheel with 7 vertices. By Observation [obs:2]2 at the start of the proof, the neighborhood of u_i forms a cycle. Moreover, by Observation [obs:1]1, the vertices t_1, t_2 and t_3 all have the same degree d. We argue that d=6. Since all u_i have degree 4, if every pair of vertices u_i, u_i+1 had a common neighbor other than v and t_i, this would have to be a single vertex adjacent to u_1, u_2 and u_3. However, such a vertex x does not exist because otherwise G' G[u_1,u_2,u_3,t_1,t_2,t_3,x,v] would be a 3-connected graph in which every face is a triangle with a saturated vertex or a 4-cycle with two saturated vertices and Lemma <ref> would imply G = G' which cannot be since G' has a vertex of degree 3, namely x. 

Thus, some pair {u_i,u_i+1} does not have a common neighbor other than v or t_i, which in turn implies d(v) = d(t_i)= 6 using Lemma <ref>. Therefore, all neighbors of v have degree 4 or 6. More strongly, we conclude that the vertex degrees that appear among the neighbors of t_i are the same as the vertex degrees appearing as neighbors of v, including multiplicites. Thus, each t_i also has 3 neighbors of degree 4. 

By Observation [obs:1]1 all vertices in N_4 only have neighbors of degree 6 (since we already know that they have 3 neighbors of degree 6). By the same argument, these degree 6 vertices have themselves 3 neighbors of degree 4 and 3 neighbors of degree 6.

We conclude that the entire graph has only vertices of degree 4 and 6. Since every face incident with v is a triangle, and v is arbitrary among the degree 6 vertices, we conclude that G is a triangulation. Moreover, every vertex of degree 4 has exactly 4 neighbors of degree 6 and every vertex of degree 6 has exactly 3 neighbors of degree 4. We conclude that 4n_4= 3n_6 where n_i is the number of vertices of G of degree i. Since n_4+n_6 = n =|G| we conclude that G has 18n/7 edges. Since G is a triangulation, it has 3n-6 edges. We conclude that 18n/7 = 3n-6 and thus G is a graph on 14 vertices. Furthermore, the graph G' induced by the vertices of degree 6 is a 3-regular graph on 8 vertices. All faces in the induced drawing of G' are 4-cycles.
We conclude that G' is the cube. (There is only one triangle-free planar 3-regular graph on 8 vertices.) Each face of G' contains, within G, a vertex of degree 4. We conclude that G is the tetrakis hexahedron.


[|N_4| = 4]  

In this case v must be incident to some diagonals, since otherwise v has degree 4. Thus, for every i ∈{1,2,3,4} the diagonal {v, x_i,i+1} must be present, since by Observation [obs:2]2 the neighbors of a degree 4 vertex form a cycle or an independent set. It follows that v must have degree 8. We obtain a graph that has at most as many vertices of degree 4 as it has vertices of degree at least 8. (Every vertex of degree at least 8 is adjacent to at least 4 vertices of degree 4 and every vertex of degree 4 is adjacent to 4 vertices of degree at least 8.) Double counting implies that the graph has at least 3n edges, which is impossible for a planar graph. 

[|N_4| ≥ 5]

We first show the following claim.

[resume]For each i∈{1,…,t}, the vertices u_i and u_i+2 have a common neighbor other than v.

We show the statement for i=1.
Assuming otherwise implies that v is a singleton in χ^1_G_(u_1,u_3). We first argue that in this coloring, the vertex u_2 is also a singleton. Again, assume otherwise. Then there must be a vertex u∈ N_4∖{u_2} that has the same color as u_2. By Claim <ref>, for i∈{1,2} the vertices u_i and u_i+1 have a common neighbor x_i,i+1 so that u_i, v,u_i+1,x_i,i+1 form a face or a face after removing a diagonal.

Thus, the vertex u must have a neighbor y_1,2 other than v that is adjacent to u_1 and a neighbor y_2,3 other than v that is adjacent to u_3. Moreover, for i∈{1,2}, the vertex x_i,i+1 should have the same color as y_i,i+1. See Figure <ref>. (Note that y_1,2≠ y_2,3 since we have assumed that u_1 and u_3 do not have a common neighbor other than v.) 





Since it holds that |N_4| ≥ 5 we know that u_4≠ u_t. Therefore u≠ u_4 or u≠ u_t. By symmetry we can assume the latter. (To see the symmetry recall that u_4 is the successor of u_3 in N_4 and u_t is the predecessor of u_1 in N_4).
Note that the cycle v,u,y_1,2,u_1 separates u_t from u_2.

Consider the area A' bounded by the cycle v,u,y_1,2,u_1 which contains u_t. Inside the area lies u'∈ N_4, the vertex that follows u in the cyclic ordering of N_4. 

Consider the set M  N(u_3)∪{u_1,v,u_3} and note that M is a union of color classes since we have assumed that u_1 and u_3 do not have a common neighbor other than v. The cycle v,u,y_1,2,u_1 contains only two vertices of M and there are no vertices inside A' that are in M. Thus, due to 3-connectivity, there must be a path from u or from y_1,2 to u' such that no inner vertex of the path is in M. Note that u' does not have the same color as u_2 since it cannot share a neighbor other than v with u_3.

Unless x_1,2= y_1,2, every path from u_2 and every path from x_1,2 to a vertex in N_4∖{u_1,u_2,u_3,u} that does not have an inner vertex in M  must pass through u or through y_1,2. This implies however that u and u_2 do not have the same color or that x_1,2 and y_1,2 do not have the same color contradicting our construction. We conclude that x_1,2=y_1,2.

By Claim <ref>, the vertices u and u' have a common neighbor other than v. If this neighbor were not x_1,2 then u could not have the same color as u_2, since there would be a path from u to u' avoiding inner vertices from M∪{y_1,2} but there would be no such path from u to any vertex in N_4∖{u_1,u_2,u_3,u}. Figure <ref> depicts this situation. We conclude that u' is a neighbor of y_1,2=x_1,2. However this makes {y_1,2,v} a separator that separates u_1 from u, since by Claim <ref>, neither u' nor u_2 have a neighbor both inside and outside of the cycle u',v,u_2,x_1,2.

Up to this point, regarding our efforts to prove the claim, we have shown that u_2 is a singleton. If x_1,2 were not adjacent to v or x_2,3 were not adjacent to v, then χ^1_G_(u_1,u_3) would have three singletons lying on the same face. So assume otherwise. We can also assume that neither x_1,2 nor x_2,3 is a singleton. But this cannot be, because the copies rendering x_1,2 and x_2,3 non-singletons (i.e., the other, necessarily existing vertices that have the same color as x_1,2 or x_2,3) should also be non-equal and adjacent to u_2 which would force u_2 to have degree at least 5. This proves the claim. 
 

Since G[N_4] is empty, a common neighbor of u_i and u_i+2 other than v must be equal to a common neighbor of u_i+1 and u_i+3 other than v. This means that there is a vertex v' other than v adjacent to all vertices of N_4.

Consider now the area bounded by the cycle v,u_i,v',u_i+1 which does not contain u_i+2. If both u_i and u_i+1 have two neighbors inside this area, then they do not have any neighbors outside the area, making {v,v'} a separator.
If u_i only has one neighbor inside the area, then this neighbor coincides with x_i,i+1 and hence must be adjacent to u_i+1. We conclude that v,u_i,x_i,i+1,u_i+1 forms a face or becomes a face after removing the diagonal {x_i,i+1,v}. A symmetric argument can be applied with regard to v' in place of v. It follows that inside the cycle v,u_i,v',u_i+1 there is at most one vertex, namely x_i,i+1.
However, we already ruled out vertices of degree 3 at the beginning of the proof, so x_i,i+1 must be adjacent to all vertices of the cycle, and thus has degree 4. This cannot be since it would then be in N_4.
We conclude that u_i does not have a neighbor inside the cycle v,u_i,v',u_i+1. A similar observation holds for the cycle v,u_i-1,v',u_i.
 However, u_i must have some neighbors within the area bounded by the cycle v,u_i,v',u_i+1 or within the area bounded by the cycle v,u_i-1,v',u_i yielding the final contradiction.
 
 



Recalling that every 3-connected planar graph has a vertex of degree 3, 4 or 5, the proof follows immediately by combining Lemma <ref> with the Lemmas <ref>, <ref>, and <ref>.




plain


 