# Kempe Equivalent List Colorings

Daniel W. Cranston Department of Computer Science, Virginia Commonwealth
University, Richmond, VA, USA<EMAIL_ADDRESS>Reem Mahmoud Department of
Mathematics and Applied Mathematics, Virginia Commonwealth University,
Richmond, VA, USA<EMAIL_ADDRESS>
###### Abstract

An $\alpha,\beta$-Kempe swap in a properly colored graph interchanges the
colors on some component of the subgraph induced by colors $\alpha$ and
$\beta$. Two $k$-colorings of a graph are $k$-Kempe equivalent if we can form
one from the other by a sequence of Kempe swaps (never using more than $k$
colors). Las Vergnas and Meyniel showed that if a graph is $(k-1)$-degenerate,
then each pair of its $k$-colorings are $k$-Kempe equivalent. Mohar
conjectured the same conclusion for connected $k$-regular graphs. This was
proved for $k=3$ by Feghali, Johnson, and Paulusma (with a single exception
$K_{2}\\!\\!\\!\\!\\!\qed\,K_{3}$, also called the 3-prism) and for $k\geq 4$
by Bonamy, Bousquet, Feghali, and Johnson.

In this paper we prove an analogous result for list-coloring. For a list-
assignment $L$ and an $L$-coloring $\varphi$, a Kempe swap is called $L$-valid
for $\varphi$ if performing the Kempe swap yields another $L$-coloring. Two
$L$-colorings are called $L$-equivalent if we can form one from the other by a
sequence of $L$-valid Kempe swaps. Let $G$ be a connected $k$-regular graph
with $k\geq 3$ and $G\neq K_{k+1}$. We prove that if $L$ is a $k$-assignment,
then all $L$-colorings are $L$-equivalent (again excluding only
$K_{2}\\!\\!\\!\\!\\!\qed\,K_{3}$). Further, if
$G\in\\{K_{k+1},K_{2}\\!\\!\\!\\!\\!\qed\,K_{3}\\}$, $L$ is a
$\Delta$-assignment, but $L$ is not identical everywhere, then all
$L$-colorings of $G$ are $L$-equivalent. When $k\geq 4$, the proof is
completely self-contained, implying an alternate proof of the result of Bonamy
et al.

Our proofs rely on the following key lemma, which may be of independent
interest. Let $H$ be a graph such that for every degree-assignment $L_{H}$ all
$L_{H}$-colorings are $L_{H}$-equivalent. If $G$ is a connected graph that
contains $H$ as an induced subgraph, then for every degree-assignment $L_{G}$
for $G$ all $L_{G}$-colorings are $L_{G}$-equivalent.

Dedicated to the memory of Landon Rabern.

##  1 Introduction

An $\alpha,\beta$-Kempe swap in a proper (partial) coloring of a graph
interchanges the colors on some component of the subgraph induced by colors
$\alpha$ and $\beta$. Thus, a Kempe swap always yields another proper
(partial) coloring. Kempe swaps were introduced in the late 1800s in an
attempt to prove the 4 Color Theorem. Given a partial proper coloring, we aim
to perform one or more Kempe swaps to reach another partial proper coloring
that can be extended to an additional vertex. By repeating this process, we
eventually color the whole graph, hopefully. This initial effort to prove the
4 Color Theorem was unsuccessful. However, Heawood salvaged the idea and used
it to prove the 5 Color Theorem. Kempe swaps are particularly useful in the
study of edge-coloring, which is equivalent to coloring line graphs.111This is
because in a line graph each subgraph recolored by a Kempe swap must be a path
or an even length cycle. So it is easier to understand how the coloring
changes after a single Kempe swap.

Although Kempe swaps are still used as a tool in constructing proper
colorings, they have also sparked a new interest. Two proper $k$-colorings of
a graph $G$ are _(Kempe) $k$-equivalent_ if we can form one from the other by
a sequence of Kempe swaps (never using more than $k$ colors). When all
$k$-colorings of a graph are $k$-equivalent, we have a natural way to sample a
$k$-coloring randomly. Starting from an arbitrary $k$-coloring, we perform a
sequence of Kempe swaps, each chosen randomly from those available in the
current coloring, until our current $k$-coloring is “almost” equally likely to
be any one of the $k$-colorings of $G$. To formalize all this, and clarify
some technical details, we would use Markov chains (which we avoid in this
paper). This problem and many related ones have been studied widely under the
name _reconfiguration_ [10, 11]. Given two instances of some type of object,
we ask whether we can “reconfigure” one to be the other, using a sequence of
reconfiguration steps. In our case, the objects are $k$-colorings and the
reconfiguration steps are Kempe swaps.

In the late 1970s, Meyniel [9] proved that if $G$ is a planar graph, then all
of its 5-colorings are 5-equivalent; see also [5]. This was extended by Las
Vergnas and Meyniel [8], who proved the same conclusion for all $K_{5}$-minor-
free graphs. They also showed that if $G$ is $(k-1)$-degenerate, then all of
its $k$-colorings are $k$-equivalent; Lemma 1 below generalizes this result to
list coloring. Mohar conjectured that if $G$ is connected and $k$-regular,
then all of its $k$-colorings are $k$-equivalent. This is a natural next step,
since the sparsest graphs that are not $(k-1)$-degenerate are $k$-regular.
Mohar’s Conjecture was proved for $k=3$ by Feghali, Johnson, and Paulusma [7]
(with a single exception $K_{2}\\!\\!\\!\\!\\!\qed\,K_{3}$) and for $k\geq 4$
by Bonamy, Bousquet, Feghali, and Johnson [1]; this was reproved in a stronger
form in [2]. In this paper our Main Theorem (stated on the next page) is an
analogous result for list-coloring.

A _block_ in a graph is a maximal 2-connected subgraph. A _list-assignment_
††margin:  block, list-assignment $L$ for a graph $G$ gives each $v\in V(G)$ a
list $L(v)$ of allowable colors. Given $L$, an _$L$ -coloring_††margin:
$L$-coloring is a proper coloring $\varphi$ such that $\varphi(v)\in L(v)$ for
all $v\in V(G)$. For an $L$-coloring $\varphi$, a Kempe swap is _$L$
-valid_††margin:  $L$-valid, $L$-equivalent (for $\varphi$) if performing the
Kempe swap on $\varphi$ yields another $L$-coloring. Two $L$-colorings are
_$L$ -equivalent_ if we can form one from the other by a sequence of $L$-valid
Kempe swaps. A _$k$ -assignment_ (resp.  _$f$ -assignment_)††margin:
$k$-/$f$-/degree- assignment to a graph $G$ is a list assignment $L$ such that
$|L(v)|=k$ (resp. $|L(v)|=f(v)$), for each $v\in V(G)$, where $k$ is some
constant (resp. $f:V(G)\to\mathbb{Z}^{+}$). A _degree-assignment_ to $G$ is a
list assignment $L$ such that $|L(v)|=d(v)$ for each $v\in V(G)$. Given $L$, a
graph $G$ is _$L$ -swappable_ if it has some $L$-coloring222By requiring at
least one $L$-coloring, we can state many of our results more cleanly. and all
of its $L$-colorings are $L$-equivalent. A graph $G$ is _degree-swappable_
††margin:  $L$-/$k$-/$f$- /degree- swappable (resp.  _$k$ -swappable_ or _$f$
-swappable_) if $G$ is $L$-swappable for every degree-assignment $L$ (resp.
$k$-assignment or $f$-assignment $L$). To illustrate some of the key ideas in
this paper, we now reprove a helpful lemma of Las Vergnas and Meyniel [8],
generalized to the context of list-coloring.

######  Lemma 1.

Let $G$ be a connected graph, let $L$ be a list-assignment for $G$, and fix
$v\in V(G)$ with $|L(v)|>d(v)$. Let $G^{\prime}:=G-v$ and let $L^{\prime}$
denote $L$ restricted to $G^{\prime}$. If $G^{\prime}$ is
$L^{\prime}$-swappable, then $G$ is $L$-swappable.

###### Proof.

Assume $G^{\prime}$ is $L^{\prime}$-swappable. Let $\varphi_{1}$ and
$\varphi_{2}$ denote $L$-colorings of $G$, and let $\varphi^{\prime}_{1}$ and
$\varphi^{\prime}_{2}$ denote their restrictions to $G^{\prime}$. Since
$G^{\prime}$ is $L^{\prime}$-swappable, there exist $L^{\prime}$-colorings
$\psi^{\prime}_{0},\ldots,\psi^{\prime}_{t}$ of $G^{\prime}$ such that
$\psi^{\prime}_{0}=\varphi^{\prime}_{1}$ and
$\psi^{\prime}_{t}=\varphi^{\prime}_{2}$ and $\psi^{\prime}_{i}$ differs from
$\psi^{\prime}_{i-1}$ by a single $L^{\prime}$-valid Kempe swap, for each
$i\in[t]$. Now we extend each $\psi^{\prime}_{i}$ to an $L$-coloring
$\psi_{i}$ of $G$ such that $\psi_{i}$ and $\psi_{i-1}$ are $L$-equivalent.
Suppose that $\psi^{\prime}_{i}$ differs from $\psi^{\prime}_{i-1}$ by an
$\alpha,\beta$-swap at $v_{i}$, for some $v_{i}\in V(G)$ and some colors
$\alpha$ and $\beta$. If $\psi_{i-1}(v)\notin\\{\alpha,\beta\\}$ or if $v$ is
not in the same $\alpha,\beta$-component of $\psi_{i-1}$ as $v_{i}$, then we
form $\psi_{i}$ from $\psi_{i-1}$ by performing the same $\alpha,\beta$-swap
at $v_{i}$. This approach also works if $\\{\alpha,\beta\\}\subseteq L(v)$ and
$v$ is in the same $\alpha,\beta$-component as $v_{i}$, but $v$ has degree 1
in that component. So suppose that $v$ is in the same $\alpha,\beta$-component
as $v_{i}$, but either $|L(v)\cap\\{\alpha,\beta\\}|=1$ or $v$ has degree at
least 2 in that $\alpha,\beta$-component. Since $|L(v)|>d(v)$, there exists
$\gamma\in L(v)$ that is unused by $\psi_{i-1}$ on the closed neighborhood of
$v$. We first recolor $v$ with $\gamma$, and then perform the
$\alpha,\beta$-swap at $v_{i}$. By induction on $i$, this gives an
$L$-coloring $\psi_{t}$ that restricts to $\psi^{\prime}_{t}$. Lastly, if
$\psi_{t}(v)\neq\varphi_{2}(v)$, then we recolor $v$ with $\varphi_{2}(v)$. ∎

######  Corollary 2.

A graph $G$ is $L$-swappable whenever there exists a vertex order in which
each vertex $x$ is preceded by fewer than $|L(x)|$ neighbors. In particular,
$G$ is $L$-swappable when $G$ is $(k-1)$-degenerate and $L$ is a
$k$-assignment. This includes the special case that $k:=\Delta$ and $G$ is
connected, but not regular.

###### Proof.

We prove the first statement by induction on $|V(G)|$. The base case
$|V(G)|=1$ holds trivially. The induction step holds by Lemma 1, taking $v$ to
be the final vertex in the order. The second statement follows from the first,
using any order that witnesses that $G$ is $(k-1)$-degenerate. Finally, the
third statement obviously follows from the second, when we order the vertices
by non-increasing distance from some vertex of degree less than $k$. ∎

Now we can state our Main Theorem and outline its proof.

######  Main Theorem.

If $G$ is a connected graph with $\Delta\geq 3$ and
$G\notin\\{K_{2}\\!\\!\\!\\!\\!\qed\,K_{3},K_{\Delta+1}\\}$, then $G$ is
$\Delta$-swappable. If
$G\in\\{K_{2}\\!\\!\\!\\!\\!\qed\,K_{3},K_{\Delta+1}\\}$ and $L$ is a
$\Delta$-assignment that is not identical everywhere, then $G$ is
$L$-swappable.

Note that the interesting case in our Main Theorem is when $G$ is regular,
since otherwise the result is included in Corollary 2. A crucial step in
proving the Main Theorem is verifying the following Key Lemma. Its proof
mirrors that of Lemma 1.

######  Key Lemma.

If $H$ is degree-swappable and $G$ is a connected graph containing $H$ as an
induced subgraph, then $G$ is degree-swappable.

In view of the Key Lemma, we have a natural plan to prove the Main Theorem.
(i) Compile a collection $\mathcal{H}$ of known degree-swappable graphs. (ii)
Show that if $G$ is connected with $\Delta\geq 3$ and
$G\notin\\{K_{2}\\!\\!\\!\\!\\!\qed\,K_{3},K_{\Delta+1}\\}$, then $G$ contains
as an induced subgraph some $H\in\mathcal{H}$. (For brevity, we omit from this
sketch the details of handling $K_{2}\\!\\!\\!\\!\\!\qed\,K_{3}$ and
$K_{\Delta+1}$, but they are not hard.) In fact, Erdös, Rubin, and Taylor [6]
used a similar approach to characterize all degree-choosable graphs. They
showed that if $G$ is connected and not a Gallai tree, then $G$ contains as an
induced subgraph an even length cycle with at most one chord333The general
case of this result easily reduces to the case when $G$ is 2-connected, which
is known as Rubin’s Block Lemma. For a shorter proof, see Section 9 of [4].,
which we call a _good cycle_ ††margin:  good cycle . It is easy to check that
every good cycle is degree-choosable. A _Gallai tree_ ††margin:  Gallai tree
is a connected graph in which each block is an odd cycle or a clique. These
results on good cycles imply that every connected graph is degree-choosable
unless it is a Gallai tree; this implication uses an analogue of our Key Lemma
that holds for degree-choosability.444To prove this analogue, we greedily
color the vertices of $G\setminus H$ in order of non-increasing distance from
$H$. Afterward, we can extend this coloring to $H$ precisely because $H$ is
degree-choosable. So perhaps we might hope to even characterize degree-
swappable graphs. But when we take this approach, we quickly find many degree-
choosable graphs that are not degree-swappable.

######  Example 1.

Denote the vertices of an $n$-cycle $C_{n}$ by $v_{1},\ldots,v_{n}$. Let
$L(v_{i})=\\{i,i+1\\}\bmod{n}$. See the left side of Figure 1. Note that
$C_{n}$ has two $L$-colorings: (1) $\varphi(v_{i})=i$, for all $v_{i}$, and
(2) $\varphi(v_{i})=i+1$, for all $v_{i}$. However, $|L(v_{i})\cap
L(v_{j})|\leq 1$ for all distinct $i,j$. Thus, neither $\varphi_{1}$ nor
$\varphi_{2}$ admits any $L$-valid Kempe swap. So $C_{n}$ is not degree-
swappable.

1 22 33 44 55 66 11 22 33 44 55 66 11 22 33 44 55 66 10 1 21 2 33 4 5 66 7 8
97 8 9 7 8 9 0 7 8 9 4 5 4 5 1 2 0 1 21 2 33 4 5 66 7 8 97 8 9 7 8 9 0 7 8 9 4
5 4 5 1 2 Figure 1: Left: A 6-cycle and a 2-assignment showing that it is not
degree-swappable. Right: Another “Gallai tree plus edge” and a degree-
assignment showing that it is not degree-swappable.

More generally, let $G$ be any Gallai tree. For each block $B_{i}$ of $G$, let
$d_{i}:=d_{B_{i}}(v)$ for all $v\in V(B_{i})$. Assign to each block $B_{i}$ a
list $L_{i}$ of size $d_{i}$ such that $L_{i_{1}}\cap L_{i_{2}}=\emptyset$
whenever $i_{1}\neq i_{2}$. Let $L(v):=\cup_{B_{i}\ni v}L_{i}$. Now $G$ is not
$L$-choosable, as is easy to verify by induction on its number of blocks.
(This is the standard construction showing that Gallai trees are not degree-
choosable.) Form $G^{\prime}$ from $G$ by adding some edge $xy$ such that
$x,y\in V(G)$ but $xy\notin E(G)$, $x$ and $y$ are in distinct blocks, and
$G^{\prime}$ is not a Gallai tree. Let $L^{\prime}(x):=L(x)\cup\\{\alpha\\}$,
$L^{\prime}(y):=L(y)\cup\\{\alpha\\}$, and $L^{\prime}(z):=L(z)$ for all $z\in
V(G)\setminus\\{x,y\\}$, and some $\alpha\notin\bigcup_{v\in V(G)}L(v)$. See
the right side of Figure 1. Note that $G^{\prime}$ is $L^{\prime}$-choosable
(by the result of Erdös, Rubin, and Taylor [6], since $G^{\prime}$ is not a
Gallai tree). Furthermore, $G^{\prime}$ has some $L^{\prime}$-coloring
$\varphi_{1}$ with $\varphi_{1}(x)=\alpha$ and has some other
$L^{\prime}$-coloring $\varphi_{2}$ with $\varphi_{2}(y)=\alpha$. Moreover,
since $G$ is not $L$-choosable, every $L^{\prime}$-coloring of $G^{\prime}$
uses $\alpha$ on either $x$ or $y$. Note that $L^{\prime}(x)\cap
L^{\prime}(y)=\\{\alpha\\}$, so no $L$-valid Kempe swap can move $\alpha$ from
$x$ to $y$, or vice versa. Thus, $\varphi_{1}$ and $\varphi_{2}$ are not
$L$-equivalent. This implies that $G^{\prime}$ is not degree-swappable, even
though, as noted above, $G^{\prime}$ is degree-choosable.

Note that Example 1 includes an even cycle with a single chord $e$ whenever
the two cycles containing $e$ each have odd length (deleting any edge besides
the chord gives a Gallai tree). Thus, many good cycles are not degree-
swappable. In fact, we have discovered further graphs that are not degree-
swappable, and we do not yet have a conjectured description of all such
graphs. So we suggest the following problem.

######  Problem 1.

Characterize all degree-swappable graphs.

To prove the Main Theorem, we split into two cases: (i) connectivity at most 3
and (ii) connectivity at least 4. In the first case, which takes most of the
work, we use a small vertex cut to show that $G$ contains an induced subgraph
$H$ from a family of known degree-swappable graphs. In the second case, the
higher connectivity allows us to more explicitly construct a sequence of
$L$-valid Kempe swaps to transform any $L$-coloring $\varphi_{1}$ into any
other $\varphi_{2}$. The rest of the paper is organized as follows. In Section
2 we prove the Key Lemma, as well as a few other helpful results on
swappability. In Section 3 we compile a family of known degree-swappable
graphs. Finally, in Section 4 we prove the Main Theorem.

##  2 Swappability Lemmas

In this section, we prove a number of lemmas about swappability. More
precisely, each lemma considers a graph $G$ and a list assignment $L$ and
identifies a set of $L$-colorings of $G$ that are pairwise $L$-equivalent.
Each of these results can be viewed as extending Lemma 1.

######  Lemma 3.

(a) If $|L(v)|\geq d(v)$ for all $v$ and $|L(w)|>d(w)$ for some $w$, then $G$
is $L$-swappable (assuming that $G$ is connected). (b) If $x\in V(G)$ and
$G-x$ is connected, then the same result holds even if we only require
$|L(x)|\geq 1$.

###### Proof.

The first statement follows directly from Corollary 2. We order the vertices
by non-increasing distance from $w$; thus, every vertex other than $w$ has a
neighbor later in the order. For the second statement, we simply put $x$ first
in the order, and apply the previous result to $G-x$, which is still
connected. ∎

Fix a graph $G$, a vertex $v\in V(G)$, a list assignment $L$ for $G$, and a
color $\alpha\in L(v)$. Let $\mathcal{L}$ denote the set of all $L$-colorings
of $G$. Let _$\mathcal{L}_{v,\alpha}$_ ††margin:  $\mathcal{L}$,
$\mathcal{L}_{v,\alpha}$ denote the set of $L$-colorings $\varphi$ such that
$\varphi(v)=\alpha$. If $\mathcal{L}^{\prime}$ is a set of $L$-colorings of
$G$ that are pairwise $L$-equivalent, then $\mathcal{L}^{\prime}$ _mixes_
††margin:  mixes . If also $\varphi$ is an $L$-coloring that is $L$-equivalent
to some $\varphi^{\prime}\in\mathcal{L}^{\prime}$, then we say that $\varphi$
_mixes with $\mathcal{L}^{\prime}$_††margin:  mixes with
$\mathcal{L}^{\prime}$ ; often it is the case that
$\varphi\notin\mathcal{L}^{\prime}$.

######  Lemma 4.

Let $G$ be a connected graph such that $w,x\in V(G)$, $wx\in E(G)$, and $G-x$
is connected. If $L$ is a degree-assignment for $G$ such that there exists
$\alpha\in L(x)\setminus L(w)$, then $\mathcal{L}_{x,\alpha}$ is nonempty and
mixes. More generally, $\cup_{\alpha\in L(x)\setminus
L(w)}\mathcal{L}_{x,\alpha}$ mixes.

###### Proof.

We let $G^{\prime}:=G-wx$, let $L^{\prime}(x):=L(x)\setminus L(w)$, and let
$L^{\prime}(v):=L(v)$ for all $v\in V(G)\setminus\\{x\\}$. Now we apply Lemma
3(b) to $G^{\prime}$ and $L^{\prime}$. ∎

######  Lemma 5.

Let $G$ be a graph with $v,w_{1},w_{2}\in V(G)$ such that
$G-\\{w_{1},w_{2}\\}$ is connected, $w_{1},w_{2}\in N(v)$, and
$w_{1}w_{2}\notin E(G)$. Fix a degree-assignment $L$ for $G$.

  1. (1)

If there exists $\alpha\in L(w_{1})\cap L(w_{2})$, then
$\mathcal{L}_{w_{1},\alpha}\cap\mathcal{L}_{w_{2},\alpha}$ is nonempty and
mixes.

  2. (2)

If there exist $\alpha\in L(w_{1})\cap L(w_{2})$ and $\beta\in
L(w_{1})\setminus L(v)$, then
$(\mathcal{L}_{w_{1},\alpha}\cap\mathcal{L}_{w_{2},\alpha})\cup\mathcal{L}_{w_{1},\beta}$
is nonempty and mixes.

  3. (3)

If there exist $\alpha\in L(w_{1})\cap L(w_{2})$ and $\beta\in
L(w_{1})\setminus L(v)$ and also $N(w_{1})=N(w_{2})$, then $\bigcup_{\alpha\in
L(w_{1})\cap
L(w_{2})}(\mathcal{L}_{w_{1},\alpha}\cup\mathcal{L}_{w_{2},\alpha})\cup\bigcup_{\beta\in
L(w_{1})\setminus L(v)}\mathcal{L}_{w_{1},\beta}$ is nonempty and mixes.

###### Proof.

To prove (1), let $G^{\prime}:=G-\\{w_{1},w_{2}\\}$, let
$L^{\prime}(y):=L(y)\setminus\\{\alpha\\}$ for all $y\in N(w_{1})\cup
N(w_{2})$, and let $L^{\prime}(z):=L(z)$ for all other $z\in V(G)$. Note that
$|L^{\prime}(v)|\geq|L(v)|-1>d_{G}(v)-2=d_{G^{\prime}}(v)$. Thus, we can apply
Lemma 3(a) to $G^{\prime}$ and $L^{\prime}$.

Now we prove (2). If $\alpha=\beta$, this holds by Lemma 4 (with $x:=w_{1}$
and $w:=v$). So assume $\alpha\neq\beta$. Let $G^{\prime}:=G-vw_{1}-w_{2}$ and
let $L^{\prime}(w_{1}):=\\{\alpha,\beta\\}$ and
$L^{\prime}(z):=L(z)\setminus\\{\alpha\\}$ for all $z\in N(w_{2})$ and
$L^{\prime}(z):=L(z)$ otherwise. Now $L^{\prime}$ mixes for $G^{\prime}$, by
Lemma 3(a), with $w:=v$. These $L^{\prime}$-colorings of $G^{\prime}$ are in
bijection with colorings of $G$ in
$\mathcal{L}_{w_{2},\alpha}\cap(\mathcal{L}_{w_{1},\alpha}\cup\mathcal{L}_{w_{1},\beta})$,
and each $L^{\prime}$-valid Kempe swap in $G^{\prime}$ maps to an $L$-valid
Kempe swap in $G$ that respects this bijection. Since
$\mathcal{L}_{w_{1},\beta}$ mixes by Lemma 4 and
$\mathcal{L}_{w_{1},\alpha}\cap\mathcal{L}_{w_{2},\alpha}$ mixes by (1), the
result follows. (Note that $L_{w_{1},\beta}\cap
L_{w_{2},\alpha}\neq\emptyset$, since we can color $w_{1}$ with $\beta$ and
color $w_{2}$ with $\alpha$, and then color $G-\\{w_{1},w_{2}\\}$ greedily
towards $v$.)

Finally, we prove (3). Consider
$\varphi\in\mathcal{L}_{w_{1},\alpha}\cup\mathcal{L}_{w_{2},\alpha}$. If
$\varphi(w_{1})\neq\varphi(w_{2})$, then we simply recolor $w_{1}$ or $w_{2}$
so that they both use color $\alpha$; this is possible because
$N(w_{1})=N(w_{2})$, so $\alpha$ is unused on $N(w_{1})$ (and on $N(w_{2})$).
Thus, $\varphi$ mixes with
$(\mathcal{L}_{w_{1},\alpha}\cap\mathcal{L}_{w_{2},\alpha})\cup\mathcal{L}_{w_{1},\beta}$
by (2). Finally, if there exist distinct $\alpha,\alpha^{\prime}\in
L(w_{1})\cap L(w_{2})$, then we repeat the argument above with
$\alpha^{\prime}$ in place of $\alpha$. Similarly, if there exist distinct
$\beta,\beta^{\prime}\in L(w_{1})\setminus L(v)$, then we repeat the argument
above with $\beta^{\prime}$ in place of $\beta$. This proves (3). ∎

We will often want to prove that a graph $G$ is $L$-swappable, for some list
assignment $L$. When we want to prove that a graph is degree-swappable, the
following lemma significantly restricts the possibilities for $L$ that we must
consider.

######  Lemma 6.

Fix a graph $G$, a degree-assignment $L$, and an edge $vw$ such that $G-vw$ is
connected and degree-choosable. If $|L(v)\cap L(w)|\leq 1$, then $G$ is
$L$-swappable.

###### Proof.

If $|L(v)\cap L(w)|=0$, then $G$ is $L$-swappable if and only if $G-vw$ is
$L$-swappable, and the latter statement holds by Lemma 3(a). So assume instead
that $|L(v)\cap L(w)|=1$ and that $L(v)\cap L(w)=\\{\alpha\\}$. Form $L_{1}$
from $L$ by removing $\alpha$ from $L(v)$. Form $L_{2}$ from $L$ by removing
$\alpha$ from $L(w)$. Form $L_{3}$ from $L$ by removing $\alpha$ from both
$L(v)$ and $L(w)$. Note that $G$ is $L_{1}$-swappable if and only if $G-vw$ is
$L_{1}$-swappable, and the latter is true by Lemma 3(a). The same is true for
$L_{2}$-swappable. Since $L_{3}$ is a degree-assignment for $G-vw$, by
assumption $G-vw$ has an $L_{3}$-coloring $\varphi$. Note that $\varphi$ is
both an $L_{1}$-coloring and an $L_{2}$-coloring. Thus, $L_{1}$-colorings mix
with $L_{2}$-colorings. Since every $L$-coloring of $G$ is either an
$L_{1}$-coloring or an $L_{2}$-coloring (or both), we conclude that $G$ is
$L$-swappable. ∎

The rest of this section is dedicated to proving the Key Lemma (from the
introduction). In fact, we prove a more general version, Lemma 7.

######  Lemma 7.

Fix a graph $G$ and a function $f:V(G)\to\mathbb{Z}^{+}$. Let $H$ be an
induced subgraph of $G$ such that $G-H$ is $f$-swappable. Let
$f^{\prime}(x):=f(x)-(d_{G}(x)-d_{H}(x))$ for all $x\in V(H)$. If
$f^{\prime}(x)\geq d_{H}(x)$ for all $x\in V(H)$ and $H$ is
$f^{\prime}$-swappable, then $G$ is $f$-swappable.

To see that Lemma 7 generalizes the Key Lemma, let $f(v):=d_{G}(v)$ for all
$v\in V(G)$, and note that $f^{\prime}(v)=d_{H}(v)$ for all $v\in V(H)$ and
$G-H$ is $f$-swappable by Lemma 3(a). (Each component of $G-H$ has a vertex
$w$ with a neighbor in $H$.)

In this paper we only need the version of the lemma from the introduction
(when $f(v)=d(v)$), but the more general version is no harder to prove, and it
is useful elsewhere [3]. The proof of Lemma 7 mirrors that of Lemma 1. We
start with $L$-colorings $\varphi_{1}^{\prime}$ and $\varphi_{2}^{\prime}$ of
$G\setminus H$ and a sequence of $L$-colorings
$\psi_{0}^{\prime},\ldots,\psi_{t}^{\prime}$, showing that
$\varphi_{1}^{\prime}$ and $\varphi_{2}^{\prime}$ are $L$-equivalent. And we
seek to extend these $L$-colorings of $G\setminus H$ to $L$-colorings of $G$.
Our main obstacle is the possibility that at some step colors used on $H$
might interfere with our desired Kempe swap. So first we prove, for every
$L$-coloring $\varphi^{\prime}$ of $G\setminus H$ and every $L$-valid Kempe
swap for $\varphi^{\prime}$, that some extension of $\varphi^{\prime}$ to an
$L$-coloring of $G$ does not interfere. This notion of “non-interference”
motivates Definition 1 and Lemma 8.

######  Definition 1.

For a graph $G$ and a list assignment $L$ for $G$, an $L$-coloring $\varphi$
of $G$ is _$(\alpha,\beta)$ -versatile_††margin:  $(\alpha,\beta)$-versatile
_at $w$_ if $\varphi(w)\in\\{\alpha,\beta\\}$ and an $(\alpha,\beta)$-swap at
$w$ is $L$-valid for $\varphi$.

######  Lemma 8.

Fix a graph $G$, a connected subgraph $H$, and a list assignment $L$ for
$V(G)$. Let $\varphi^{\prime}$ be an $L$-coloring for $G-H$ that is
$(\alpha,\beta)$-versatile at a vertex $w$. If $|L(v)|\geq d_{G}(v)$ for all
$v\in V(H)$, and $H$ is not a Gallai tree, then there exists an $L$-coloring
$\varphi$ of $G$ that extends $\varphi^{\prime}$ such that $\varphi$ is
$(\alpha,\beta)$-versatile at $w$. Further, there exists such an $L$-coloring
$\varphi$ with the property that each $(\alpha,\beta)$-component of $\varphi$
contains the vertex set of at most one $(\alpha,\beta)$-component of
$\varphi^{\prime}$.

###### Proof.

Since $H$ is not a Gallai tree, it contains an induced even cycle, $C$, with
at most one chord. We first show how to extend $\varphi^{\prime}$ to $G-C$,
and then how to extend it to all of $G$.

A key step is to show that if $|V(H)|\geq 2$ and $x\in V(H)$, then there
exists an $L$-coloring $\varphi$ of $G-(H-x)$ that extends $\varphi^{\prime}$
to $x$ and that is $(\alpha,\beta)$-versatile at $w$. Suppose that $|V(H)|\geq
2$ and fix $x\in V(H)$. When choosing a color for $x$ (for brevity, we denote
it by $\varphi^{\prime}(x)$), to ensure that the resulting extension of
$\varphi^{\prime}$ is an $L$-coloring that is $(\alpha,\beta)$-versatile at
$w$, we need to check the following three properties: (a)
$\varphi^{\prime}(x)\neq\varphi^{\prime}(y)$ for all $y\in N(x)\setminus H$,
(b) if $\varphi^{\prime}(x)\in\\{\alpha,\beta\\}$ and $x$ has a neighbor
$y\notin H$ with $\varphi^{\prime}(y)\in\\{\alpha,\beta\\}$, then
$\\{\alpha,\beta\\}\subseteq L(x)$, and (c) if
$\varphi^{\prime}(x)\in\\{\alpha,\beta\\}$, then $x$ has at most one neighbor
$y\notin H$ with $\varphi^{\prime}(y)\in\\{\alpha,\beta\\}$. Now (a) ensures
the extension is a proper $L$-coloring; (b) ensures that an
$(\alpha,\beta)$-swap at $w$ will not create a problem at $x$; and (c) ensures
that each $(\alpha,\beta)$-component of $\varphi$ contains at most one
$(\alpha,\beta)$-component of $\varphi^{\prime}$ and that an
$(\alpha,\beta)$-swap at $w$ will not create a problem at $y$.

We form a list assignment $L^{\prime}(x)$ from $L(x)$ by first removing each
color that is used by $\varphi^{\prime}$ on a neighbor of $x$. Further, if
$\alpha$ is used on a neighbor of $x$ and $\alpha\notin L(x)$, then we remove
$\beta$ from $L(x)$. Similarly, if $\alpha$ is used on two neighbors of $x$,
then we remove $\beta$ from $L(x)$, regardless of whether or not $\alpha\in
L(x)$. We also remove $\alpha$ from $L(x)$ if either of these situations
occurs, but with $\beta$ and $\alpha$ interchanged. Since $|L(x)|\geq
d_{G}(x)$, we must have $|L^{\prime}(x)|\geq d_{H}(x)\geq 1$, because $H$ is
connected and $|V(H)|\geq 2$. To extend $\varphi^{\prime}$ to $x$, we simply
choose any color in $L^{\prime}(x)$. This completes the key step, started in
the previous paragraph. To extend $\varphi^{\prime}$ to $G-C$, we repeatedly
apply the key step, coloring vertices in order of non-increasing distance from
$C$. Now we show how to extend $\varphi^{\prime}$ to $C$.

Case 1: $\bm{C}$ has no chord. For each $v\in V(C)$, form $L^{\prime}(v)$ as
in the previous paragraph. Again, $|L^{\prime}(v)|\geq 2$ for all $v\in V(C)$.
First suppose there exists $\gamma$ and $x,y\in V(C)$ such that
$\gamma\notin\\{\alpha,\beta\\}$ and $xy\in E(C)$ and $\gamma\in
L^{\prime}(x)\setminus L^{\prime}(y)$. Now we color $x$ with $\gamma$ and
proceed around $C$ finishing with $y$. Each time that we color a vertex on
$C$, we ensure that its degree in the subgraph induced by vertices colored
$\alpha$ and $\beta$ (among all colored vertices, both inside and outside $C$)
is at most 1. This ensures that each $(\alpha,\beta)$-component of $\varphi$
contains the vertex set of at most one $(\alpha,\beta)$-component of
$\varphi^{\prime}$. This process succeeds because each time we color another
vertex $z_{1}$ we reduce the number of allowable colors on its uncolored
neighbor $z_{2}$ by at most one (even if we completely repeat the process of
removing colors as in the previous paragraph, treating $z_{1}$ as though it is
outside $H$); this is virtually the same as extending $\varphi^{\prime}$ to
$G-C$. We can finish at $y$ because the color on $x$ does not restrict our
choice of color for $y$.

Suppose instead there exists $\gamma\notin\\{\alpha,\beta\\}$ such that
$\gamma\in L^{\prime}(v)$ for all $v\in C$. Now we use $\gamma$ on one maximum
independent set in $C$ and color each remaining vertex $v$ from
$L^{\prime}(v)\setminus\\{\gamma\\}$.

Finally, suppose that $L^{\prime}(v)=\\{\alpha,\beta\\}$ for each $v\in V(C)$.
Now we alternate $\alpha$ and $\beta$ around $C$. In each case, it is easy to
check that the resulting coloring $\varphi$ is $(\alpha,\beta)$-versatile at
$w$. The key observation for this last case is that no vertex of $C$ has a
neighbor in $G-C$ colored $\alpha$ or $\beta$, by construction of
$L^{\prime}(v)$.

Case 2: $\bm{C}$ has a chord. Let $x$ denote one endpoint of the chord and let
$y$ and $z$ denote the neighbors of $x$ on $C$, besides the other endpoint of
the chord. Form $L^{\prime}(v)$ for each $v\in V(C)$, as above; again
$|L^{\prime}(v)|\geq d_{H}(v)$ for all $v\in V(C)$. Since $|L^{\prime}(x)|\geq
d_{H}(x)=3$, there exists $\gamma\in
L^{\prime}(x)\setminus\\{\alpha,\beta\\}$. If $\gamma\in L^{\prime}(y)\cap
L^{\prime}(z)$, then use $\gamma$ on $y$ and $z$ and color greedily toward $x$
in the remaining uncolored subgraph. So assume instead that $\gamma\notin
L^{\prime}(y)\cap L^{\prime}(z)$; by symmetry, assume that $\gamma\notin
L^{\prime}(z)$. Now use $\gamma$ on $x$, then color the remaining uncolored
subgraph greedily in order of non-increasing distance from $z$. Again, we can
finish at $z$ because using $\gamma$ on $x$ does not restrict the choice of
color for $z$. As above, each time that we color a vertex on $C$, we ensure
that its degree in the subgraph induced by vertices colored $\alpha$ and
$\beta$ (both inside and outside $C$) is at most 1. Again, this ensures that
each $(\alpha,\beta)$-component of $\varphi$ contains the vertex set of at
most one $(\alpha,\beta)$-component of $\varphi^{\prime}$. ∎

Now we prove Lemma 7. As mentioned above, the proof mirrors that of Lemma 1,
but now Lemma 8 ensures some extension to $H$ is versatile for the next Kempe
swap in $G-H$.

###### Proof of Lemma 7..

Fix a graph $G$ and a function $f:V(G)\to\mathbb{Z}^{+}$. Let $H$ be an
induced subgraph of $G$ such that $G-H$ is $f$-swappable. Let
$f^{\prime}(x):=f(x)-(d_{G}(x)-d_{H}(x))$ for all $x\in V(H)$. Assume that
$f^{\prime}(x)\geq d_{H}(x)$ for all $x\in V(H)$ and that $H$ is
$f^{\prime}$-swappable.

Let $L$ be an $f$-assignment for $G$. Let $G^{\prime}:=G-H$. By assumption,
each component of $G^{\prime}$ is $L$-swappable. So $G^{\prime}$ is
$L$-swappable. Let $\varphi_{0}$ and $\varphi$ be two $L$-colorings of $G$,
and let $\varphi_{0}^{\prime}$ and $\varphi^{\prime}$ denote their
restrictions to $G^{\prime}$. Since $G^{\prime}$ is $L$-swappable, there
exists a sequence
$\varphi_{0}^{\prime},\varphi_{1}^{\prime},\ldots,\varphi_{k}^{\prime}=\varphi^{\prime}$
of $L$-colorings of $G^{\prime}$ such that every two successive $L$-colorings
differ by a single $L$-valid Kempe swap. By induction on $k$, we extend each
$\varphi_{i}^{\prime}$ to an $L$-coloring $\varphi_{i}$ of $G$ such that every
two successive $L$-colorings in the sequence
$\varphi_{0},\varphi_{1},\ldots,\varphi_{k}=\varphi$ are $L$-equivalent. The
case $k=0$ is easy because $\varphi_{0}=\varphi$, so we are done.

So assume that $k\geq 1$. Suppose that $\varphi_{i+1}^{\prime}$ differs from
$\varphi_{i}^{\prime}$ by an $\alpha,\beta$-swap at a vertex $v_{i}$. By Lemma
8, there exists an $L$-coloring $\widetilde{\varphi_{i}}$ of $G$, such that
the restriction of $\widetilde{\varphi_{i}}$ to $G^{\prime}$ is
$\varphi^{\prime}_{i}$ and an $\alpha,\beta$-swap at $v_{i}$ is $L$-valid in
$\widetilde{\varphi_{i}}$. Furthermore, the restriction of this new coloring
(after performing the $\alpha,\beta$-swap at $v_{i}$) is
$\varphi_{i+1}^{\prime}$. It now suffices to show that $\varphi_{i}$ and
$\widetilde{\varphi_{i}}$ are $L$-equivalent. We do this by a sequence of
Kempe swaps that recolors $H$ but never changes the colors on $V(G-H)$.

For each $v\in V(G-H)$, remove $\varphi^{\prime}_{i}(v)$ from $L(w)$ for each
$w\in N(v)\cap V(H)$; denote the resulting list assignment on $H$ by $L_{H}$.
Note that $|L_{H}(x)|\geq f^{\prime}(x)\geq d_{H}(x)$ for all $x\in V(H)$. If
$|L_{H}(x)|>f^{\prime}(x)$ for some $x$, then $H$ is $L_{H}$-swappable by
Corollary 2, since $|L_{H}(y)|\geq f^{\prime}(y)\geq d_{H}(y)$ for all $y\in
H$. So assume $|L_{H}(y)|=f^{\prime}(y)$ for all $y\in H$. Since $H$ is
$f^{\prime}$-swappable, the restrictions of $\varphi_{i}$ and
$\widetilde{\varphi_{i}}$ to $H$ (which are both $L_{H}$-colorings) are
$L_{H}$-equivalent. Consider a sequence of Kempe swaps that witnesses this.
Note that performing the same Kempe swaps in $G$ transforms $\varphi_{i}$ to
$\widetilde{\varphi_{i}}$ (this is because for each edge $vw$ with $v\in V(H)$
and $w\notin V(H)$, we have $\varphi^{\prime}_{i}(w)\notin L_{H}(v)$). Now
performing an $\alpha,\beta$-swap at $v_{i}$ in $\widetilde{\varphi_{i}}$
yields an $L$-coloring of $G$ that restricts to $\varphi^{\prime}_{i+1}$ on
$H$; denote this $L$-coloring of $G$ by $\varphi_{i+1}$.

The previous two paragraphs show that we can use $L$-valid Kempe swaps to
transform $\varphi_{0}$ into an $L$-coloring $\widetilde{\varphi}$ that agrees
with $\varphi$ on $G-H$. Finally, we transform $\widetilde{\varphi}$ to
$\varphi$. This is possible precisely because $H$ is $f^{\prime}$-swappable. ∎

##  3 Degree-swappable Graphs

In this section we prove that various graphs are degree-swappable. In view of
Lemma 7, if a connected $k$-regular graph $G$ contains an induced copy of any
degree-swappable graph, then $G$ is $k$-swappable. Our first example of
degree-swappable graphs requires a new definition. A _theta graph_ ††margin:
theta graph , $\Theta_{a,b,c}$, consists of two 3-vertices, $x$ and $y$, that
are linked by internally disjoint paths of lengths $a$, $b$, and $c$.

######  Lemma 9.

If $G$ is a bipartite theta graph, $\Theta_{a,b,c}$, then $G$ is degree-
swappable.

###### Proof.

Fix a degree-assignment $L$ for $G$. Note that $G-vw$ is degree-choosable for
all $vw\in E(G)$. So, by Lemma 6, $|L(v)\cap L(w)|\geq 2$ for all $vw\in
E(G)$. Let $x$ and $y$ denote the 3-vertices of $G$, and let $P_{a},P_{b}$,
and $P_{c}$ denote the internally disjoint $x,y$-paths of lengths $a$, $b$,
and $c$, respectively. Since $G$ has an $x,y$-path with all internal vertices
of degree 2, by Lemma 6 we can assume, by transitivity, that $|L(x)\cap
L(y)|\geq 2$.

Suppose $L(x)\neq L(y)$. Specifically, suppose $L(x)=\\{1,2,3\\}$ and
$L(y)=\\{1,2,4\\}$. This implies that every 2-vertex has the list $\\{1,2\\}$.
Fix an arbitrary $L$-coloring $\varphi$ of $G$ with $\varphi(x)=3$ and
$\varphi(y)=4$. Starting from an arbitrary $L$-coloring $\varphi^{\prime}$, we
can recolor $x$ with 3 and recolor $y$ with 4, then reach $\varphi$ by using
at most one $1,2$-swap on each path of $G-\\{x,y\\}$. Thus, we assume that
$L(x)=L(y)=\\{1,2,3\\}$.

Suppose two disjoint $x,y$-paths, say $P_{a}$ and $P_{b}$, have the same list
for their 2-vertices. Form $G^{\prime}$ from $G$ by deleting all 2-vertices of
$P_{a}$. Note that $d_{G^{\prime}}(x)=2<3=|L(x)|$, so $G^{\prime}$ is
$L$-swappable by Lemma 3(a) with $w:=x$. This implies that $G$ is also
$L$-swappable, as follows. Since $P_{a}$ and $P_{b}$ have lengths of the same
parity, given any $L$-coloring of $G$, we can recolor the internal vertices of
$P_{a}$ so the neighbors of $x$ and $y$ on $P_{a}$ have the same colors as
their neighbors on $P_{b}$. Thus, any sequence of Kempe swaps in $G^{\prime}$
extends to a sequence in $G$. So we assume that no two $x,y$-paths have the
same list for their 2-vertices.

Denote by $x_{a}$, $x_{b}$, and $x_{c}$ the 2-neighbors of $x$, if they exist
(when one $x,y$-path has no 2-vertices, assume it is $P_{c}$, and let $x_{c}$
denote $y$). Assume $L(x_{a})=\\{1,2\\}$, $L(x_{b})=\\{1,3\\}$, and
$L(x_{c})=\\{2,3\\}$. Note that the sets
$\mathcal{L}_{x,1},\mathcal{L}_{x,2}$, and $\mathcal{L}_{x,3}$ each mix by
Lemma 4.

Consider $\varphi\in\mathcal{L}_{x_{a},1}\cap\mathcal{L}_{x_{b},1}$. Note that
the 2,3-component containing $x$ is a path (also containing all 2-vertices of
$P_{c}$ and possibly $y$, depending on the parities of the $x,y$-paths). So a
2,3-swap at $x$ shows that $\mathcal{L}_{x,2}$ mixes with $\mathcal{L}_{x,3}$.
By symmetry, $\mathcal{L}_{x,1}$ mixes with $\mathcal{L}_{x,2}$. Thus,
$\mathcal{L}_{x,1}\cup\mathcal{L}_{x,2}\cup\mathcal{L}_{x,3}$ mixes; that is,
$\mathcal{L}$ mixes. ∎

Recall that an even length cycle with at most one chord is a _good cycle_.

######  Lemma 10.

Let $G$ be a graph that contains as induced subgraphs two good cycles, $H_{1}$
and $H_{2}$. Assume that $H_{1}$ and $H_{2}$ intersect in at most one vertex
and that all but at most one edge induced by $V(H_{1})\cup V(H_{2})$ either
lies in $H_{1}$ or lies in $H_{2}$; further, if there exists such an edge,
then $V(H_{1})\cap V(H_{2})=\emptyset$. If $P$ is a shortest path from $H_{1}$
to $H_{2}$, then $G[V(H_{1})\cup V(H_{2})\cup V(P)]$ is degree-swappable.
Thus, if $G$ is a connected graph with at least two degree-choosable blocks,
then $G$ is degree-swappable.

Figure 2: Three examples of $G[V(H_{1})\cup V(H_{2})\cup V(P)]$ in Lemma 10.

###### Proof.

To begin, we prove the second statement from the first. Let $B_{1}$ and
$B_{2}$ be two degree-choosable blocks of $G$. So neither $B_{1}$ nor $B_{2}$
is a complete graph or odd cycle. By Rubin’s Block Lemma [6], there exist
induced even cycles $H_{1}$ and $H_{2}$, each with at most one chord, in
$B_{1}$ and $B_{2}$, respectively. Let $P$ be a shortest path from $H_{1}$ to
$H_{2}$. By the first statement and the Key Lemma, $G$ is degree-swappable.

Now we prove the first statement. If possible, choose $H_{1}$ so that it is an
even cycle with at most one chord that is closest to $H_{2}$. By Lemma 7, it
suffices to consider the case that $V(G)=V(H_{1})\cup V(H_{2})\cup V(P)$. Let
$L$ be a degree-assignment for $G$. Let $u$ be the endpoint of $P$ in $H_{1}$.
For each path $Q$, let _$\ell(Q)$_ ††margin:  $\ell(Q)$ denote the length
(number of edges) of $Q$. We often write the _parity of $Q$_††margin:  parity
of $Q$ to mean the parity of $\ell(Q)$. If $\ell(P)\neq 0$, let $v$ be the
neighbor of $u$ on $P$. Suppose $N_{H_{1}}(v)=\\{w_{1},\dots,w_{t}\\}$ with
$t\geq 3$. Let $P_{i}$ be the $w_{i},w_{i+1}$-path in $H_{1}$ for every
$i\in[t]$. If $P_{i}$ is even for some $i\in[t]$, then $G[v\cup V(P_{i})]$ is
an even cycle closer to $H_{2}$, contradicting our choice of $H_{1}$. So
assume $P_{i}$ is odd for every $i\in[t]$. Since $H_{1}$ is even, $t$ must
also be even; thus, $t\geq 4$. But now $G[v\cup V(P_{1})\cup V(P_{2})]$ is an
even cycle closer to $H_{2}$. Thus, when $\ell(P)\neq 0$, we assume
$|N_{H_{1}}(v)|\leq 2$.

Also, since $G-xy$ is degree-choosable for every $xy\in E(H_{1})$, we assume
$|L(x)\cap L(y)|\geq 2$ by Lemma 6. Thus, if $w,z\in V(H_{1})$ and some
$w,z$-walk consists only of 2-vertices (including $w$ and $z$), then
transitivity implies $L(w)=L(z)$.

Case 1: $\bm{\ell(P)=0}$ or $\bm{|N_{H_{1}}(v)|=1}$.

Case 1.1: $\bm{H_{1}}$ has no chord. Pick $u_{1},u_{2}\in N_{H_{1}}(u)$ and
let $L(u_{1})=\\{a,b\\}$; see Figure 3(a). As observed above,
$L(u_{2})=L(u_{1})=L(u_{i})$ for all $u_{i}\in V(H_{1})\setminus\\{u\\}$, by
transitivity. Since $H_{1}$ is even, $\varphi(u_{1})=\varphi(u_{2})$ for every
$\varphi\in\mathcal{L}$. By Corollary 2, $\mathcal{L}_{u_{1},a}$ and
$\mathcal{L}_{u_{1},b}$ each mix. To see this, order the vertices of $G-H_{1}$
by non-increasing distance from $u$ (with $u$ last), and recall that always
$\varphi(u_{1})=\varphi(u_{2})$. Now we show that
$\mathcal{L}_{u_{1},a}\cup\mathcal{L}_{u_{1},b}$ mixes. Since $H_{2}$ is
degree-choosable and $|L(u)|=d(u)=3$, there exists an $L$-coloring
$\varphi^{\prime}$ with $\varphi^{\prime}(u)\notin\\{a,b\\}$. Performing an
$a,b$-swap at $u_{1}$ in $\varphi^{\prime}$ shows that $\mathcal{L}_{u_{1},a}$
mixes with $\mathcal{L}_{u_{1},b}$. Thus, $\mathcal{L}$ mixes.

Case 1.2: $\bm{H_{1}}$ has a chord $\bm{xy}$ with $\bm{u\notin\\{x,y\\}}$. Let
$P_{1}$, $P_{2}$, and $P_{3}$ be the $x,y$-path, $x,u$-path, and $y,u$-path on
$H_{1}$ avoiding $u$, $y$, and $x$, respectively; see Figure 3(b). If
$\ell(P_{1})$ is odd, then $\ell(P_{2}\cup P_{3})$ is also odd since $H_{1}$
is even. Thus, $H_{1}$ induces a bipartite theta graph, and we are done by
Lemma 9. So we instead assume $\ell(P_{1})$ is even.

$u_{1}$$u_{2}$$u$ (a)

$P_{1}$$P_{2}$$P_{3}$$x$$y$$u$ (b)

$P_{1}$$P_{2}$$x$$y$ (c)

Figure 3: The 3 subcases in Case 1. (a) Case 1.1: $H_{1}$ has no chord. (b)
Case 1.2: $H_{1}$ has a chord $xy$. (c) Case 1.3: $H_{1}$ has a chord $uy$
(i.e. $x=u$).

Assume $L(w)=\\{a,b\\}$ for every 2-vertex $w$ on $P_{1}$. Recall that
$\\{a,b\\}\subseteq L(x)\cap L(y)$. Let $L(x)=\\{a,b,c\\}$. Suppose $L(y)\neq
L(x)$; so assume $L(y)=\\{a,b,d\\}$. By Lemma 4, both $\mathcal{L}_{x,c}$ and
$\mathcal{L}_{y,d}$ mix (and are nonempty). Further,
$\mathcal{L}_{x,c}\cap\mathcal{L}_{y,d}\neq\emptyset$, since $H_{2}$ is
degree-choosable; thus, $\mathcal{L}_{x,c}\cup\mathcal{L}_{y,d}$ mixes. Since
$G[V(P_{1})]$ is an odd cycle,
$\mathcal{L}=\mathcal{L}_{x,c}\cup\mathcal{L}_{y,d}$, and we are done. So we
instead assume that $L(x)=L(y)=\\{a,b,c\\}$.

Since $H_{1}$ and $\ell(P_{1})$ are both even, $\ell(P_{2})$ and $\ell(P_{3})$
have the same parity. By Lemma 4, $\mathcal{L}_{x,c}$ and $\mathcal{L}_{y,c}$
each mix (and are nonempty). Further,
$\mathcal{L}=\mathcal{L}_{x,c}\cup\mathcal{L}_{y,c}$. So it suffices to show
that $\mathcal{L}_{x,c}$ mixes with $\mathcal{L}_{y,c}$. Pick $x_{1}\in
N_{P_{2}}(x)$ and $y_{1}\in N_{P_{3}}(y)$, if they exist; again, see Figure
3(b).

Suppose first that neither $P_{2}$ nor $P_{3}$ has any internal vertex. Since
$|L(u)\cap L(x)|\geq 2$, assume that $a\in L(u)$. Since $\ell(P_{1})$ is even,
we can color $V(H_{1})$ so that all neighbors of $x$ and $y$ use color $a$.
Since $H_{2}$ is degree-choosable, we can extend this coloring to an
$L$-coloring $\varphi$ of $G$. Now performing a $b,c$-swap at $x$ shows that
$\mathcal{L}_{x,c}$ mixes with $\mathcal{L}_{y,c}$, and we are done.

Assume instead that $P_{2}$ or $P_{3}$ contains an internal 2-vertex. By
symmetry, assume $x_{1}$ exists. Let $w_{1}$ be a 2-vertex adjacent to $x$ on
$P_{1}$. Recall that $L(w_{1})=\\{a,b\\}$. As above, we assume $a\in
L(x_{1})$. Now $\mathcal{L}_{w_{1},a}\cap\mathcal{L}_{x_{1},a}$ mixes by Lemma
5. To construct an $L$-coloring in this set, we can color $x$ arbitrarily from
$L(x)\setminus\\{a\\}$ and color greedily toward $H_{2}$. Thus,
$\mathcal{L}_{w_{1},a}\cap\mathcal{L}_{x_{1},a}$ contains $\varphi_{1}$ and
$\varphi_{2}$ such that $\varphi_{1}(x)=c$ and such that $\varphi_{2}(x)=b$,
so $\varphi_{2}(y)=2$. This again proves that $\mathcal{L}_{x,c}$ mixes with
$\mathcal{L}_{y,c}$, so we are done.

Case 1.3: $\bm{H_{1}}$ has a chord $\bm{xy}$ with $\bm{x=u}$ (by symmetry).
Let $P_{1}$ and $P_{2}$ be the $u,y$-paths in $H_{1}$; see Figure 3(c). Since
$H_{1}$ is even, $\ell(P_{1})$ and $\ell(P_{2})$ have the same parity. If
$\ell(P_{1})$ is odd, then $H_{1}$ induces a bipartite theta graph, and we are
done by Lemma 9. So $\ell(P_{1})$ is even. Pick $y_{1}\in N_{P_{1}}(y)$ and
$y_{2}\in N_{P_{2}}(y)$. By symmetry, assume $L(y)=\\{a,b,c\\}$ and
$L(y_{1})=\\{a,b\\}$. By Lemma 4, $\mathcal{L}_{y,c}$ is nonempty and mixes.
By Lemma 4, $\mathcal{L}_{y,c}$ mixes.

Suppose $L(y_{2})=L(y_{1})=\\{a,b\\}$. Pick $\varphi\in\mathcal{L}_{y,a}$. We
show that $\varphi$ is $L$-equivalent to some
$\varphi^{\prime}\in\mathcal{L}_{y,c}$. If $\varphi(x)\neq c$, then recoloring
$y$ with $c$ gives a coloring in $\mathcal{L}_{y,c}$. So assume
$\varphi(x)=c$. If $\varphi(w)=b$ for some $w\in N_{G-E(H_{1})}(x)$, then
there exists $\alpha\in L(x)$ which does not appear on $N[x]$. We recolor $x$
with $\alpha$ then recolor $y$ with $c$ to get a coloring in
$\mathcal{L}_{y,c}$. So assume $\varphi(w)\neq b$ for every $w\in
N_{G-E(H_{1})}(x)$. Now we perform an $a,b$-swap at $y$ followed by a
$b,c$-swap at $y$ to get a coloring in $\mathcal{L}_{y,c}$. The same argument
shows that every $\varphi\in\mathcal{L}_{y,b}$ is $L$-equivalent to some
coloring in $\mathcal{L}_{y,c}$. Since $\mathcal{L}_{y,c}$ mixes, also
$\mathcal{L}_{y,a}\cup\mathcal{L}_{y,b}\cup\mathcal{L}_{y,c}$ mixes; that is,
$\mathcal{L}$ mixes.

So we assume $L(x_{1})\neq L(y_{1})$. By symmetry, assume
$L(y_{1})=\\{a,c\\}$. By Lemma 4, both $\mathcal{L}_{y,b}$ and
$\mathcal{L}_{y,c}$ mix (and are nonempty). Further, $\mathcal{L}_{y,a}$ is
nonempty. And for every $\varphi\in\mathcal{L}_{y,a}$, we can perform an
$a,b$-swap (resp. $a,c$-swap) at $y$ to get a coloring in $\mathcal{L}_{y,b}$
(resp. $\mathcal{L}_{y,c}$). Thus,
$\mathcal{L}_{y,a}\cup\mathcal{L}_{y,b}\cup\mathcal{L}_{y,c}$ mixes; that is,
$\mathcal{L}$ mixes.

Case 2: $\bm{|N_{H_{1}}(v)|=2}$. Let $N_{H_{1}}(v)=\\{v_{1},v_{2}\\}$; denote
the $v_{1},v_{2}$-paths in $H_{1}$ by $P_{1}$ and $P_{2}$. Recall, from the
start of the proof, that $P_{1}$ and $P_{2}$ are both odd.

Case 2.1: $\bm{H_{1}}$ has no chord. By symmetry, assume $\ell(P_{2})>1$. Pick
$w_{1}\in N_{P_{2}}(v_{1})$ and $w_{2}\in N_{P_{2}}(v_{2})$; see Figure 4(a).
Assume $L(v_{1})=\\{a,b,c\\}$ and $L(w_{1})=\\{a,b\\}$, by symmetry. Suppose
$L(v_{1})\neq L(v_{2})$; specifically, suppose $L(v_{2})=\\{a,b,d\\}$. By
Lemma 4, both $\mathcal{L}_{v_{1},c}$ and $\mathcal{L}_{v_{2},d}$ mix. By
Lemma 6, if $\ell(P_{1})>1$, then $L(w)=\\{a,b\\}$ for every $w\in V(P_{1})$.
Thus, $\mathcal{L}_{v_{1},c}\cap\mathcal{L}_{v_{2},d}\neq\emptyset$. Further,
for every $\varphi\notin\mathcal{L}_{v_{1},c}\cup\mathcal{L}_{v_{2},d}$, there
exists $\gamma\in(\\{c,d\\}-\varphi(v))$. So we can perform a Kempe swap
either at $v_{1}$ or at $v_{2}$ to get a coloring in
$\mathcal{L}_{v_{1},c}\cup\mathcal{L}_{v_{2},d}$. Thus, $\mathcal{L}$ mixes,
and we are done. So we assume instead that $L(v_{1})=L(v_{2})=\\{a,b,c\\}$.

$v$$v_{1}$$v_{2}$$w_{1}$$w_{2}$$P_{1}$$P_{2}$ (a)

$v$$v_{1}$$v_{2}$$s$$t$$P_{1}$$P_{s}$$P_{t}$ (b)

$v$$v_{1}$$v_{2}$$s$$t$$P_{3}$$P_{4}$$P_{5}$$P_{6}$ (c)

$v$$s$$t$$v_{2}$$P_{1}$$P_{3}$$P_{4}$ (d)

Figure 4: The 4 instances of Case 2, when $H_{1}$ contains 2 neighbors of $v$:
the first comprises Case 2.1 and the remaining three comprise Case 2.2. (a)
$H_{1}$ has no chord. (b) $H_{1}$ has a chord $st$ on $P_{2}$. (c) $H_{1}$ has
a chord $st$ on $P_{1}\cup P_{2}$. (d) $H_{1}$ has a chord $v_{1}t$ (i.e.
$s=v_{1}$).

By Lemma 4, $\mathcal{L}_{v_{1},c}$ and $\mathcal{L}_{v_{2},c}$ each mix. If
$\ell(P_{1})=1$ or $L(w)=\\{a,b\\}$ for every $w\in V(P_{1})$, then
$\mathcal{L}_{v_{1},a}$ and $\mathcal{L}_{v_{1},b}$ each mix by Lemma 3(a),
with $w:=v_{2}$. This is because $\varphi(w_{2})=\varphi(v_{1})$ for every
$\varphi\in\mathcal{L}_{v_{1},a}\cup\mathcal{L}_{v_{1},b}$. Similarly,
$\mathcal{L}_{v_{2},a}$ and $\mathcal{L}_{v_{2},b}$ each mix. Further,
$\mathcal{L}_{v_{1},a}\cap\mathcal{L}_{v_{2},b}\neq\emptyset$. Also, for every
$\gamma\in\\{a,b\\}$, the set
$\mathcal{L}_{v_{1},c}\cap\mathcal{L}_{v_{2},\gamma}\neq\emptyset$ and
$\mathcal{L}_{v_{2},c}\cap\mathcal{L}_{v_{1},\gamma}\neq\emptyset$. So
$\mathcal{L}_{v_{1},a}\cup\mathcal{L}_{v_{1},b}\cup\mathcal{L}_{v_{1},c}$
mixes; that is, $\mathcal{L}$ mixes. Thus, we assume $\ell(P_{1})>1$. Pick
$y_{1}\in N_{P_{1}}(v_{1})$ and $y_{2}\in N_{P_{1}}(v_{2})$. By the above, we
may assume $L(y_{1})=L(y_{2})=\\{a,c\\}$.

By Lemma 4, $\mathcal{L}_{v_{1},b}$ and $\mathcal{L}_{v_{2},b}$ each mix.
Also, $\mathcal{L}_{v_{1},c}\cap\mathcal{L}_{v_{2},b}\neq\emptyset$ and
$\mathcal{L}_{v_{1},b}\cap\mathcal{L}_{v_{2},c}\neq\emptyset$. We note that
$\mathcal{L}=\mathcal{L}_{v_{1},c}\cup\mathcal{L}_{v_{1},b}\cup\mathcal{L}_{v_{2},c}\cup\mathcal{L}_{v_{2},b}$.
So it suffices to show that $\mathcal{L}_{v_{2},c}\cup\mathcal{L}_{v_{2},b}$
mixes. As before, $\mathcal{L}_{v_{1},a}$ mixes by Lemma 3(a), with
$w:=v_{2}$. Moreover,
$\mathcal{L}_{v_{1},a}\cap\mathcal{L}_{v_{2},b}\neq\emptyset$ and
$\mathcal{L}_{v_{1},a}\cap\mathcal{L}_{v_{2},c}\neq\emptyset$. Thus,
$\mathcal{L}_{v_{2},c}\cup\mathcal{L}_{v_{2},b}$ mixes, and we are done.

Case 2.2: $\bm{H_{1}}$ has a chord $\bm{st}$. Recall, from the start of the
proof, that $H_{1}$ is an even cycle (with at most one chord) closest to
$H_{2}$; further, $\ell(P_{1})$ and $\ell(P_{2})$ are odd. Assume $s,t\in
V(P_{2})-\\{v_{1},v_{2}\\}$ (with $s$ closer to $v_{1}$). Let $P_{s}$ (resp.
$P_{t}$) be the $s,v_{1}$-path (resp. $t,v_{2}$-path) avoiding $t$ (resp.
avoiding $s$); see Figure 4(b). If $P_{s}$ and $P_{t}$ have the same parity,
then $G[H_{1}]$ is a bipartite theta graph (since $H_{1}$ is even), and we are
done by Lemma 9. So assume $P_{s}$ and $P_{t}$ have opposite parities. Now
$H_{1}[V(P_{s})\cup V(P_{t})\cup v]$ is an even cycle closer to $H_{2}$,
contradicting our assumption. The same argument works (interchanging $P_{1}$
and $P_{2}$) if $s,t\in V(P_{1})-\\{v_{1},v_{2}\\}$.

Assume instead that $s\in V(P_{1})-\\{v_{1},v_{2}\\}$ and $t\in
V(P_{2})-\\{v_{1},v_{2}\\}$. Let $P_{3}$, $P_{4}$, $P_{5}$, and $P_{6}$ be the
$v_{1},s$-path, $v_{2},s$-path, $v_{1},t$-path, and $v_{2},t$-paths forming
$P_{1}$ and $P_{2}$; see Figure 4(c). By symmetry, assume $P_{3}$ is even and
$P_{4}$ is odd. Now $P_{5}$ is even and $P_{6}$ is odd; otherwise, $G[H_{1}]$
is a bipartite theta graph, and we are done by Lemma 9. But
$H_{1}[V(P_{4})\cup V(P_{5})\cup v]$ is an even cycle closer to $H_{2}$,
contradicting our choice of $H_{1}$.

So the chord $st$ must have an endpoint in $\\{v_{1},v_{2}\\}$; say $s=v_{1}$.
Note that $t\neq v_{2}$; otherwise, $G[H_{1}]$ is a bipartite theta graph, and
we are done by Lemma 9. By symmetry, assume $t$ is on $P_{2}$. Let $P_{3}$ and
$P_{4}$ be the $s,t$ and $v_{2},t$-paths forming $P_{2}$; see Figure 4(d). Now
$P_{3}$ is even and $P_{4}$ is odd; otherwise, $G[H_{1}]$ is a bipartite theta
graph, and we are done by Lemma 9. But again $H_{1}[V(P_{4})\cup v\cup s]$ is
an even cycle closer to $H_{2}$, contradicting our choice of $H_{1}$. ∎

$x$$v$$y$$w$$P$ Figure 5: A $K_{4}^{+}$ formed by subdividing an edge one or
more times, and the resulting path $P$.

######  Lemma 11.

The graph $K_{4}^{+}$ formed from $K_{4}$ by subdividing a single edge one or
more times is degree-swappable.

###### Proof.

Let $P$ be the path formed by subdividing the edge in $K_{4}$ one or more
times. Denote the 3-vertices of $G$ by $v,w,x,y$, where $v$ and $w$ each have
a 2-neighbor; see Figure 5. Let $L$ be a degree-assignment for $G$. By
symmetry and by Lemma 6, we assume that $L(z)=\\{1,2\\}$ for every $z\in V(P)$
and $\\{1,2\\}\subseteq L(v)\cap L(w)$. By symmetry, assume that
$L(v)=\\{1,2,3\\}$.

Assume first that $L(w)=L(v)=\\{1,2,3\\}$. By Lemma 4, each of
$\mathcal{L}_{v,3}$ and $\mathcal{L}_{w,3}$ mix. Moreover,
$\mathcal{L}_{v,3}\cap\mathcal{L}_{w,3}\neq\emptyset$. Thus,
$\mathcal{L}_{v,3}\cup\mathcal{L}_{w,3}$ mixes. Let
$\mathcal{L}_{1}:=\mathcal{L}_{v,3}\cup\mathcal{L}_{w,3}$ and
$\mathcal{L}_{2}:=\mathcal{L}\setminus\mathcal{L}_{1}$. We now show that every
$\varphi\in\mathcal{L}_{2}$ mixes with $\mathcal{L}_{1}$; thus $\mathcal{L}$
mixes. Pick $\varphi\in\mathcal{L}_{2}$ and assume by symmetry that
$\varphi(v)=1$. If $3\notin\\{\varphi(x),\varphi(y)\\}$, then we recolor $v$
with 3 to get a coloring in $\mathcal{L}_{1}$, and we are done. So assume by
symmetry that $\varphi(x)=3$. Now suppose $\varphi(w)=1$. If $1\notin L(x)$,
there exists $\gamma\in L(x)$ with $\gamma\notin\cup_{z\in N[x]}\varphi(z)$.
So we recolor $x$ with $\gamma$ then recolor $v$ with 3, and we are done. If,
instead, $1\in L(x)$, then a 1,3-swap at $v$ gives a coloring in
$\mathcal{L}_{1}$, and we are done. So assume instead that $\varphi(w)=2$. If
$1\notin L(x)$, then $2\in L(x)$ by Lemma 6. Now a 2,3-swap at $w$ gives a
coloring in $\mathcal{L}_{1}$, and we are done. If, instead, $1\in L(x)$, then
a 1,3-swap at $v$ gives a coloring in $\mathcal{L}_{1}$, and we are done.

Instead assume $L(w)\neq L(v)$; specifically, assume $L(w)=\\{1,2,4\\}$. By
Lemma 4, the sets $\mathcal{L}_{v,3}$ and $\mathcal{L}_{w,4}$ each mix. Let
$\mathcal{L}_{1}:=\mathcal{L}_{v,3}\cup\mathcal{L}_{w,4}$ and
$\mathcal{L}_{2}=:\mathcal{L}\setminus\mathcal{L}_{1}$. We show that
$\mathcal{L}_{1}$ mixes. If $\\{3,4\\}\not\subseteq L(x)\cap L(y)$ or
$L(x)\neq L(y)$, then $\mathcal{L}_{v,3}\cap\mathcal{L}_{w,4}\neq\emptyset$;
thus, $\mathcal{L}_{1}$ mixes. Otherwise, $L(x)=L(y)=\\{3,4,\alpha\\}$ with
$\alpha\in\\{1,2\\}$ by Lemma 6. By symmetry, assume $L(x)=L(y)=\\{3,4,1\\}$.
We show again that $L_{1}$ mixes.

Suppose $\ell(P)$ is even. Pick
$\varphi\in\mathcal{L}_{v,2}\cap\mathcal{L}_{w,2}\cap\mathcal{L}_{x,3}\cap\mathcal{L}_{y,4}$.
Now we can recolor either $x$ with 1 then $v$ with 3, or $y$ with 1 then $w$
with 4 to get colorings in $\mathcal{L}_{v,3}$ and $\mathcal{L}_{w,4}$,
respectively. Thus, $\mathcal{L}_{1}$ mixes. Instead assume that $\ell(P)$ is
odd. Pick
$\varphi_{1}\in\mathcal{L}_{v,1}\cap\mathcal{L}_{w,2}\cap\mathcal{L}_{x,3}\cap\mathcal{L}_{y,4}$
and
$\varphi_{2}\in\mathcal{L}_{v,2}\cap\mathcal{L}_{w,1}\cap\mathcal{L}_{x,3}\cap\mathcal{L}_{y,4}$.
Now a 1,3-swap at $v$ in $\varphi_{1}$ or a 1,4-swap at $w$ in $\varphi_{2}$
give colorings in $\mathcal{L}_{v,3}$ and $\mathcal{L}_{w,4}$, respectively.
Also, $\varphi_{1}$ and $\varphi_{2}$ are $L$-equivalent, as witnessed by a
1,2-swap at $v$. Thus, $\mathcal{L}_{1}$ mixes.

Finally, we show that every $\varphi^{*}\in\mathcal{L}_{2}$ mixes with
$\mathcal{L}_{1}$; thus, $\mathcal{L}$ mixes. Pick
$\varphi^{*}\in\mathcal{L}_{2}$ with $\varphi^{*}(v)=1$, by symmetry. Note
that $\\{\varphi^{*}(x),\varphi^{*}(y)\\}=\\{3,4\\}$; otherwise, we can either
recolor $v$ with 3 or $w$ with 4 to get a coloring in $\mathcal{L}_{1}$, and
we are done. So assume $\varphi^{*}(x)=3$ and $\varphi^{*}(y)=4$. If $\ell(P)$
is odd, then we assume $\varphi^{*}(v)=1$ and $\varphi^{*}(w)=2$; if not, then
we achieve this with a 1,2-swap at $v$. Now a 1,3-swap at $v$ shows that
$\varphi^{*}$ mixes with $\mathcal{L}_{1}$. Instead assume that $\ell(P)$ is
even. Now assume $\varphi^{*}(v)=\varphi^{*}(w)=2$; if not, then we achieve
this by a 1,2-swap at $v$. Recolor $x$ with 1, then recolor $v$ with 3. ∎

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$w$ Figure 6: The 4-wheel.

Let $W_{4}:=C_{4}\vee K_{1}$; this is the “4-wheel”, or wheel with 4 spokes
(see Figure 6).

######  Lemma 12.

The graph $W_{4}$ is degree-swappable.

###### Proof.

Let $G:=W_{4}$. Denote the 3-vertices by $v_{1},v_{2},v_{3},v_{4}$, in order
along a 4-cycle, and denote the dominating vertex by $w$; see Figure 6. Fix a
degree assignment $L$ for $G$. Note that $|L(x)\cap L(y)|\geq 2$ for all
$xy\in E(G)$, by Lemma 6. Since $|L(v_{1})\cap L(v_{2})|\geq 2$ and
$|L(v_{2})\cap L(v_{3})|\geq 2$ and $|L(v_{2})|=3$, we conclude from
Pigeonhole that $|L(v_{1})\cap L(v_{3})|\geq 1$. We consider the three cases
$|L(v_{1})\cap L(v_{3})|\in\\{1,2,3\\}$.

Case 1: $\bm{|L(v_{1})\cap L(v_{3})|=3}$. Assume $L(v_{1})=L(v_{3})$. If
$L(v_{2})\neq L(v_{1})$, then there exists $\beta\in L(v_{1})\setminus
L(v_{2})$ since $|L(v_{2})|=|L(v_{1})|$. Further, since $L(v_{1})=L(v_{3})$,
we have $L(v_{1})\cap L(v_{3})=L(v_{1})$ so $\cup_{\alpha\in L(v_{1})\cap
L(v_{3})}\mathcal{L}_{v_{1},\alpha}=\mathcal{L}$. By Lemma 5(3), $\mathcal{L}$
mixes. So assume $L(v_{2})=L(v_{1})$ and, by symmetry, $L(v_{4})=L(v_{1})$. So
there exists $\alpha\in L(w)\setminus\bigcup_{i=1}^{4}L(v_{i})$, and clearly
$\mathcal{L}_{w,\alpha}$ mixes. Given an $L$-coloring $\varphi$ with
$\varphi(w)\neq\alpha$, we can simply recolor $w$ with $\alpha$. Thus,
$\mathcal{L}$ mixes.

Case 2: $\bm{|L(v_{1})\cap L(v_{3})|=2}$. Assume that $L(v_{1})=\\{a,b,c\\}$
and $L(v_{3})=\\{a,b,d\\}$. If $\\{c,d\\}\not\subseteq L(v_{2})\cap
L(v_{4})\cap L(w)$, then $\mathcal{L}$ mixes by Lemma 5(3), as above. So
assume $\\{c,d\\}\subseteq L(v_{2})\cap L(v_{4})\cap L(w)$. By Case 1 and
symmetry, we assume $L(v_{2})\neq L(v_{4})$. Interchanging $v_{2}$ and $v_{4}$
with $v_{1}$ and $v_{3}$ (and interchanging $c$ and $d$ with $a$ and $b$)
shows that also $a,b\in L(w)$. Further, $L(v_{2})\cup L(v_{4})\subseteq L(w)$.
Thus, $L(v_{2})=\\{a,c,d\\}$ and $L(v_{4})=\\{b,c,d\\}$, up to possibly
swapping $v_{2}$ and $v_{4}$. Now by Lemma 5(3), both
$\bigcup_{\alpha\in\\{a,b\\}}\mathcal{L}_{v_{1},\alpha}\cup\mathcal{L}_{v_{3},\alpha}$
and
$\bigcup_{\alpha\in\\{c,d\\}}\mathcal{L}_{v_{2},\alpha}\cup\mathcal{L}_{v_{4},\alpha}$
mix. The union of these two sets is all of $\mathcal{L}$. Further, the two
sets mix, since some coloring $\varphi$ lies in both; namely,
$\varphi(v_{1})=\varphi(v_{3})=a$, $\varphi(v_{2})=\varphi(v_{4})=c$, and
$\varphi(w)=d$. Thus, $\mathcal{L}$ mixes.

Case 3: $\bm{|L(v_{1})\cap L(v_{3})|=1}$. Assume $L(v_{1})=\\{a,b,c\\}$ and
$L(v_{3})=\\{a,d,e\\}$. By symmetry between $v_{1},v_{3}$ and $v_{2},v_{4}$,
we assume that $|L(v_{2})\cap L(v_{4})|=1$. Since $|L(v_{i})\cap L(v_{j})|\geq
2$ for all $i\in\\{1,3\\}$ and $j\in\\{2,4\\}$, we assume that
$L(v_{2})=\\{a,b,d\\}$ and $L(v_{4})=\\{a,c,e\\}$. Since $c\in
L(v_{1})\setminus L(v_{2})$, Lemma 5(3) shows that
$\mathcal{L}_{v_{1},a}\cup\mathcal{L}_{v_{1},c}$ mixes. Since $b\in
L(v_{1})\setminus L(v_{4})$, Lemma 5(3) shows that
$\mathcal{L}_{v_{1},a}\cup\mathcal{L}_{v_{1},b}$ mixes. Thus, $\mathcal{L}$
mixes. ∎

##  4 Proof of Main Theorem

In this section, we prove our main result: Every connected $k$-regular graph
(with $k\geq 3$) is $k$-swappable unless $G=K_{k+1}$ or
$G=K_{2}\,\square\,K_{3}$. Further, these exceptional graphs are $L$-swappable
whenever $L$ is a $\Delta$-assignment that is not identical everywhere. We
split the main result into 4 cases depending on the connectivity of $G$. In
Theorem 1, we prove the result for connectivity 1. In Theorem 2, we prove the
result for connectivity 2 by using a cut set of size 2 (a 2-cut), and showing
that $G$ contains an induced degree-swappable subgraph from the family of
graphs compiled in Section 3.

For connectivity 3, we split into three cases: (i) $k\geq 5$, which we prove
in Lemma 13, (ii) $k=4$, which we prove in Lemma 14, and (iii) $k=3$, which we
prove in Lemma 15. For cases (i) and (ii) we use a 3-cut and show that $G$
contains an induced degree-swappable subgraph from Section 3. For case (iii),
we first show that for every 3-assignment $L$ of $G$, the lists must be
identical for all vertices. Then, in Theorem 3, we invoke the result of
Feghali, Johnson, and Paulusma for 3-colorings of 3-regular graphs [7, Theorem
1] (for completeness, we state it below). Finally, we prove the result for
4-connected graphs in Theorem 4 as follows. In Lemmas 16 and 17, we handle the
case of $k$-assignments $L$ that are not identical for all vertices (Lemma 17
handles the case $G=K_{k+1}$). In Lemma 18, we show that either $G$ contains a
4-wheel (so we are done by Lemma 12), or the absence of a 4-wheel restricts
the possible $L$-colorings enough that $G$ must be $L$-swappable.

######  Theorem A.

[7, Theorem 1] If $G$ is a connected 3-regular graph that is neither $K_{4}$
nor the graph $K_{2}\,\square\,K_{3}$, then all 3-colorings of $G$ are
3-equivalent.

######  Theorem 1.

For $k\geq 3$, if $G$ is $k$-regular with connectivity 1, then $G$ is
$k$-swappable.

###### Proof.

Since $G$ has connectivity 1, it contains a cut-vertex. Thus, $G$ contains at
least two endblocks. If $G$ contains at most one degree-choosable block, then
some endblock $B$ is not degree-choosable. Let $v$ be the cut-vertex in $B$.
Since $k\geq 3$ and $G$ is $k$-regular, $B=K_{k+1}$ and $d_{B}(v)=k$. But now
$G=B$ which contradicts that $G$ has connectivity 1. Thus, $G$ contains at
least two degree-choosable endblocks. By Lemma 10, $G$ is $k$-swappable. ∎

Now we consider the case that $G$ has a vertex cut of size at most 3. In a
graph $G$, a block is _Gallai_ ††margin:  Gallai if it an odd cycle or a
clique; otherwise it is _non-Gallai_ ††margin:  non-Gallai .

######  Theorem 2.

For $k\geq 3$, if $G$ is $k$-regular with connectivity 2, then $G$ is
$k$-swappable.

###### Proof.

Let $G$ satisfy the hypotheses of the theorem, and let $L$ be a $k$-assignment
for $G$. Let $S$ be a 2-cut in $G$. Let $G_{S}:=G-S$††margin:  $G_{S}$ . Now
every endblock $B$ of $G_{S}$ has order at least $k-1$, since each vertex $v$
of $B$ has $d_{G}(v)=k$ and $v$ has at most two edges to $S$. Further, if an
endblock $B$ is non-Gallai, then $B$ contains an even cycle with at most one
chord.555Recall that Rubin’s Block Lemma [6] says a block contains such a
cycle if and only if it is non-Gallai. We call such a cycle a _good cycle_
††margin:  good cycle . If $G_{S}$ has at least two endblocks each of which
contains a good cycle, then Lemma 10 implies that $G$ is $L$-swappable. So we
assume that at most one endblock of $G_{S}$ contains a good cycle. Thus, at
most one endblock of $G_{S}$ is non-Gallai.

######  Claim 1.

$G_{S}$ has at most two Gallai endblocks.

Proof. Observe that every Gallai endblock $B$ is regular of degree either
$k-1$ or $k-2$, since $|S|=2$. Further, every such $B$ sends at least $k-1$
edges to $S$. This holds because either (i) $B$ is regular of degree $k-1$, so
$B$ has at least $k$ vertices, and at least $k-1$ of these each send an edge
to $S$, or (ii) $B$ is regular of degree $k-2$, so $B$ has at least $k-1$
vertices, and at least $k-2$ of these each sends two edges to $S$.

Suppose, contrary to the claim, that $S$ contains at least 3 Gallai endblocks,
$B_{1}$, $B_{2}$, $B_{3}$. As noted above, each $B_{i}$ sends $S$ at least
$k-1$ edges. So $3(k-1)\leq 2k$; thus, $k=3$. Further, $G_{S}$ has no other
endblocks. But now some $B_{i}$ is its own component, so it contains no cut-
vertex, and thus sends more edges to $S$ than counted above, which gives a
contradiction.  $\diamondsuit$

######  Claim 2.

$G_{S}$ has exactly one non-Gallai endblock; call it $B_{0}$.

Proof. Suppose $G_{S}$ has no non-Gallai endblocks. Since $G_{S}$ has at most
two (Gallai) endblocks, each endblock is its own component. So each endblock
sends $S$ at least $\min\\{2\cdot(k-1),1\cdot k\\}=k$ edges, for a total of at
least $2k$ edges to $S$. If either component of $G_{S}$ is $(k-2)$-regular,
then $S$ has too many incident edges, so we get a contradiction. Thus, each
endblock is $K_{k}$. If either vertex in $S$ has at least 2 neighbors in each
component of $G_{S}$, then we are done by Lemma 10. So assume that each vertex
of $S$ sends one edge to one component and sends $k-1$ edges to the other. Now
$G$ contains a copy of $K_{4}^{+}$, and we are done by Lemma 11. Thus, instead
$G_{S}$ has exactly one non-Gallai endblock; call it $B_{0}$.  $\diamondsuit$

Case 1: $\bm{G_{S}}$ has exactly one Gallai endblock; call it $\bm{B_{1}}$. If
$B_{1}$ is $(k-1)$-regular, then some $v\in S$ has at least two neighbors in
$B_{1}$, but does not dominate $B_{1}$. Thus, $B_{1}+v$ contains a good cycle,
and so does $B_{0}$. Now we are done by Lemma 10. So assume instead that
$B_{1}$ is $(k-2)$-regular and that $B_{1}$ has order at least $k-1$. In fact,
each vertex of $S$ is adjacent to all of $B_{1}$. Now counting edges shows
that $B_{1}=K_{k-1}$, each vertex of $S$ is adjacent to all of $B_{1}$, and
$S$ is an independent set. Hence, $G$ contains a copy of $K_{4}^{+}$, and we
are done by Lemma 11.

Case 2: $\bm{G_{S}}$ has exactly 2 Gallai endblocks, $\bm{B_{1}}$ and
$\bm{B_{2}}$. Suppose that $B_{1}$ or $B_{2}$ is its own component; by
symmetry, say that it is $B_{1}$. If $B_{1}$ is $(k-1)$-regular, then some
vertex $x\in S$ has at least two neighbors in $B_{1}$, but does not dominate
it. So $B_{1}+x$ and $B_{0}$ each contain good cycles, and we are done by
Lemma 10. If $B_{1}$ is $(k-2)$-regular, then it sends at least $2(k-1)$ edges
to $S$. So the total number of edges incident to $S$ is at least
$2(k-1)+(k-1)+1=3k-2>2k$, a contradiction.

Thus, $B_{1}$ and $B_{2}$ are in the same component $G_{2}$ of $G_{S}$ and
$B_{0}$ is its own component $G_{1}$. Now $S$ sends $2(k-1)$ edges to non-cut-
vertices in endblocks of $G_{2}$. This implies, by counting edges to $S$, that
every other vertex of $G_{2}$ is non-adjacent to every vertex in $S$.

If some vertex $x\in S$ sends at least two edges to $B_{1}$, then (since $x$
sends no edges to the cut-vertex in $B_{1}$) $G_{S}$ has a good cycle in
$B_{0}$ and another good cycle in $B_{1}+x$, so we are done by Lemma 10. The
same is true if some $x\in S$ sends at least two edges to $B_{2}$. So assume
that each $x\in S$ sends at most one edge to $B_{1}$ and one edge to $B_{2}$.
Since $B_{1}$ and $B_{2}$ each receive at least $k-1$ edges from $S$, this
implies that $k=3$ and each $x\in S$ sends exactly one edge to each of $B_{1}$
and $B_{2}$. Now $G_{2}+x$ must contain a good cycle, unless
$B_{1}=B_{2}=K_{2}$ and $G_{2}+x$ is an odd cycle. But in this case, each
vertex of $G_{2}$ that is not a non-cut-vertex of $B_{1}$ or $B_{2}$ has too
few incident edges, a contradiction. ∎

######  Lemma 13.

For $k\geq 5$, if $G$ is $k$-regular with connectivity 3, then $G$ is
$k$-swappable.

###### Proof.

Let $G$ satisfy the hypotheses of the lemma, and let $L$ be a $k$-assignment
for $G$. Let $S$ be a minimal 3-cut of $G$, and let $G_{S}:=G-S$††margin:
$G_{S}$ .

######  Claim 1.

Every Gallai endblock $B$ of $G_{S}$ is regular of degree $k-1$, $k-2$, or
$k-3$ and sends at least $k-1$ edges to $S$. If $B$ is a component of $G_{S}$,
then $B$ sends at least $k$ edges to $S$.

Proof. Since $G$ is $k$-regular and $|S|=3$, every non-cut-vertex in an
endblock $B$ sends at most 3 edges to $S$, so sends at least $k-3$ edges to
vertices of $B$. Since $B$ is a Gallai endblock, $B$ is regular. And since $G$
is 3-connected, some non-cut-vertex of $B$ sends an edge to $S$. Thus, $B$ is
regular of degree $k-1$, $k-2$, or $k-3$.

Note that every Gallai endblock $B$ of $G_{S}$ sends at least $k-1$ edges to
$S$. This is because either (i) $B$ is $(k-1)$-regular, so at least $k-1$
vertices of $B$ each send 1 edge to $S$, or (ii) $B$ is $(k-2)$-regular, so at
least $k-2$ vertices of $B$ each send 2 edges to $S$, or (iii) $B$ is
$(k-3)$-regular, so at least $(k-3)$ vertices of $B$ each send 3 edges to $S$.
Thus, the number of edges that $B$ sends to $S$ is at least
$\min\\{1\cdot(k-1),2\cdot(k-2),3\cdot(k-3)\\}=k-1$. Further, if a component
of $G_{S}$ consists of a single block, say $B$, then a similar computation
shows that the number of edges $B$ sends to $S$ is at least $k$.
$\diamondsuit$

######  Claim 2.

$G_{S}$ has no endblock $B$ that is an odd cycle with length at least 5.

Proof. If such a $B$ exists, then it sends at least $4(k-2)$ edges to $S$. By
Claim 1, each component not containing $B$ sends at least $k$ edges to $S$.
But $4\cdot(k-2)+k=5k-8>3k$, a contradiction.  $\diamondsuit$

######  Claim 3.

$G_{S}$ has at most 1 non-Gallai endblock and at most 3 Gallai endblocks.

Proof. If $G_{S}$ contains at least 2 non-Gallai endblocks, then it contains 2
good cycles; so $G$ is degree-swappable, by Lemma 10. So instead $G_{S}$
contains at most one non-Gallai endblock. If $G_{S}$ has at least 4 Gallai
endblocks, then by Claim 1 the number of edges from $S$ to endblocks of
$G_{S}$ is at least $4(k-1)>3k$, a contradiction. So $G_{S}$ has at most 3
Gallai endblocks.  $\diamondsuit$

We will show $G$ contains an induced degree-swappable subgraph, so we are done
by Lemma 7. Specifically, we will often show $G$ contains two good cycles, and
invoke Lemma 10.

Case 1: $\bm{G_{S}}$ has 0 non-Gallai endblocks. Let $B_{1}$ be an endblock
that is a whole component $G_{1}$. If $B_{1}=K_{k-2}$, then each vertex in $S$
is adjacent to all of $B_{1}$ (and some pair of vertices in $S$ is non-
adjacent), so $G$ contains an induced $K_{4}^{+}$; thus, we are done by Lemma
11. So instead $B_{1}\in\\{K_{k-1},K_{k}\\}$. Suppose $B_{1}=K_{k}$. Now some
vertex $x\in S$ is adjacent to at least two vertices of $B_{1}$ and also non-
adjacent to some vertex $y\in B_{1}$; see Figure 7(a). (This follows from
Pigeonhole and the fact that each vertex of $S$ has a neighbor in $B_{1}$.)
Choose $z\in N(y)\cap S$. Since $x$ and $z$ each have a neighbor in $G_{2}$,
the subgraph $G[S\cup V(G_{2})]$ contains an $x,z$-path. Note that $N(x)\cap
N(z)\cap V(B_{1})=\emptyset$, since each vertex of $B_{1}$ has a unique
neighbor in $S$. Thus, $G$ contains a copy of $K_{4}^{+}$ (possibly using the
edge $xz$, rather than an $x,z$-path through $G_{2}$), and we are done by
Lemma 11.

Assume instead that $B_{1}=K_{k-1}$. Now each vertex of $B_{1}$ has exactly
two neighbors in $S$. Denote $S$ by $\\{x_{1},x_{2},x_{3}\\}$. By symmetry,
there exist vertices $y_{1},y_{2},y_{3}\in B_{1}$ such that $y_{1}$ and
$y_{2}$ are both adjacent to each of $x_{1}$ and $x_{2}$; and $y_{3}$ is
adjacent to $x_{2}$ and $x_{3}$. Now $\\{x_{1},y_{1},y_{2},y_{3}\\}$ induces
$K_{4}-e$. Since $x_{3}$ is adjacent to $y_{3}$ (but not $y_{1}$ or $y_{2}$),
again $G$ contains $K_{4}^{+}$ as above, so we are done by Lemma 11.

Case 2: $\bm{G_{S}}$ has exactly 1 non-Gallai endblock, $\bm{B_{1}}$. Let
$G_{1}$ be the component of $G_{S}$ containing $B_{1}$, and let $B_{2}$ be a
regular endblock of another component $G_{2}$. Since $S$ sends at least $k-1$
edges to $B_{2}$, by Pigeonhole some vertex $x\in S$ sends at least 2 edges to
$B_{2}$. If $B_{2}$ has at least $k$ vertices, then $x$ is not adjacent to all
of $B_{2}$, since $x$ sends an edge to $G_{1}$. Thus, $B_{2}+x$ is non-Gallai,
so it contains a good cycle. Since $B_{2}+x$ and $B_{1}$ each contain a good
cycle, we are done by Lemma 10.

Assume instead that $B_{2}$ has order $k-1$ or $k-2$. We will show that
$G_{2}=B_{2}$. Assume the contrary; so $B_{2}$ has a cut-vertex $y$; see
Figure 7(b). If $B_{2}$ has order $k-2$, then $d_{G_{2}}(y)\geq
d_{B_{2}}(y)+1=(|B_{2}|-1)+1=k-2$; so
$d_{G[S\cup\\{y\\}]}(y)=k-d_{G_{2}}(y)\leq 2$ However, each other vertex of
$B_{2}$ is adjacent to all of $S$. So some $x\in S$ is not adjacent to $y$ but
sends at least two edges to $B_{2}$. Thus, $B_{2}+x$ and $B_{1}$ each contain
a good cycle, so we are done by Lemma 10.

Assume instead that $B_{2}$ has order $k-1$; again, see Figure 7(b). The
number of edges from $S$ to $B_{2}$ is at least $2(k-2)$, and
$d_{G_{2}}(y)\geq 1+d_{B_{2}}(y)=1+((k-1)-1)=k-1$, so
$d_{G[S\cup\\{y\\}]}(y)\leq 1$. Thus, $S$ sends $y$ at most 1 edge and in
total sends all other vertices of $B_{2}$ at least $2(k-2)$ edges. If two
vertices of $S$ each send only one edge to $B_{2}$, then some non-cut-vertex
of $B_{2}$ has too few incident edges. This is because each non-cut-vertex of
$B_{2}$ needs an edge from at least 2 vertices of $S$, and $B_{2}$ has at
least $(k-2)\geq 3$ non-cut-vertices. So at least 2 vertices of $S$ send at
least 2 edges to $B_{2}$, and at least one of them is non-adjacent to $y$. We
let $x$ denote such a vertex. Now $B_{1}$ and $B_{2}+x$ each contain a good
cycle, and we are done by Lemma 10. Thus, we assume that $G_{2}=B_{2}$.

$B_{2}$$x$$z$$y$$B_{1}$$S$$G_{2}$ (a)

$B_{2}$$B_{1}$$y$$G_{1}$$S$$G_{2}$ (b)

Figure 7: $S$ and the components of $G_{S}$ when (a) $G_{1}$ is a single
Gallai endblock $B_{1}$, and (b) $G_{1}$ contains a non-Gallai endblock
$B_{1}$ and $G_{2}$ has more than one endblock.

Suppose $B_{2}$ has $k-1$ vertices. Now $S$ sends $B_{2}$ exactly $2(k-1)$
edges. Thus, some vertex $x\in S$ sends at least two edges to $B_{2}$ and is
not adjacent to all of $B_{2}$; this is because $(k-1)+2(1)<2(k-1)<2(k-1)+1$.
(The first term represents the possibility of at most one vertex of $S$
sending at least two edges to $B_{1}$ and the third term represents the
possibility of at least two vertices of $S$ dominating $B_{1}$.) Now $B_{2}+x$
contains a good cycle, as does $B_{1}$, so we are done by Lemma 10. Hence,
$B_{2}$ has $k-2$ vertices, and every vertex in $S$ is adjacent to all of
$B_{2}$. At least one pair in $S$ is not adjacent; call it $x_{1},x_{2}$. Each
of $x_{1}$ and $x_{2}$ has a neighbor in $G_{1}$, so $G$ contains a copy of
$K_{4}^{+}$, and we are done by Lemma 11. ∎

######  Lemma 14.

If $G$ is a $4$-regular graph with connectivity 3, then $G$ is $k$-swappable.

###### Proof.

Let $S$ be a vertex cut of size 3, and let $G_{S}:=G-S$††margin:  $G_{S}$ . As
in the proof of Lemma 13, if $G_{S}$ has at least two non-Gallai endblocks,
then we are done by Lemma 10. So we assume that $G_{S}$ has at most one non-
Gallai endblock.

######  Claim 1.

Each Gallai endblock of $G_{S}$ is $K_{2}$, $K_{3}$, or $K_{4}$.

Proof. The proofs of Claims 1 and 2 in Lemma 13 also work here essentially
unchanged. So each Gallai endblock is regular of degree $k-1$, $k-2$, or
$k-3$. (Here $k=4$.) As before, if $G_{S}$ has an endblock $B$ that is an odd
cycle with length at least 5, then the number of edges going to $S$ is at
least $4(k-2)+k$. However, we can strengthen this bound as follows. If $B$ is
its own component, then the number of edges it sends to $S$ is at least
$5(k-2)$. And if $B$ is not its own component, then some other endblock in its
component sends $S$ at least $k-1$ edges. Thus, we get
$\min\\{4\cdot(k-2)+(k-1),5(k-2)\\}+k>3k$, again a contradiction.
$\diamondsuit$

Case 1: $\bm{G_{S}}$ has exactly 1 non-Gallai endblock $\bm{B_{1}}$.††margin:
$B_{1}$, $G_{1}$ Let $G_{1}$ be the component of $G_{S}$ containing $B_{1}$.
Let $B_{2}$ be a Gallai endblock in some other component $G_{2}$.††margin:
$B_{2}$, $G_{2}$

Case 1.1: $\bm{B_{2}}$ is $\bm{K_{4}}$. Now $G_{2}+x$ contains a good cycle,
for some $x\in S$, as follows (so we are done by Lemma 10). If some vertex $x$
of $S$ sends at least 2 edges to $B_{2}$, then $B_{2}+x$ is non-Gallai, since
$x$ is also non-adjacent to some vertex in $B_{2}$ (this includes the case
that $G_{2}=B_{2}$). Thus, $x+B_{2}$ contains a good cycle. Otherwise, each
vertex of $S$ sends one edge to $B_{2}$ and some vertex $x$ sends an edge to
another endblock of $G_{2}$. Now $x+G_{2}$ is 2-connected and irregular (so it
is non-Gallai and contains a good cycle).

Case 1.2: $\bm{B_{2}}$ is $\bm{K_{3}}$. Suppose that no vertex of $S$ sends
edges to exactly 2 vertices of $B_{2}$. Now $G_{2}\neq B_{2}$, two vertices of
$S$ each send a single edge to $B_{2}$, and at least one of them, call it $x$,
sends an edge to another endblock of $G_{2}$. Now $G_{2}+x$ is 2-connected and
irregular; thus, it contains a good cycle. So we assume some vertex $x\in S$
sends exactly two edges to $B_{2}$. Now $B_{2}+x$ is non-Gallai and contains a
good cycle. Since $B_{1}$ is non-Gallai, we are done by Lemma 10.

Case 1.3: $\bm{B_{2}}$ is $\bm{K_{2}}$. By symmetry, we assume that every
Gallai endblock in $G_{2}$ is $K_{2}$. If $G_{2}=K_{2}$, then $G$ contains a
copy of $K_{4}^{+}$ (with its non-adjacent 3-vertices in $S$), so we are done
by Lemma 11. If $G_{2}$ contains at least 3 endblocks, then each non-cut-
vertex in each of these endblocks is adjacent to all of $S$, so $G$ contains
an induced $K_{2,3}$ (with two vertices in $S$), which is a bipartite theta
graph, so we are done by Lemma 9. Thus, $G_{2}$ has exactly two endblocks. If
$G_{2}=P_{3}$, then some $x$ in $S$ is adjacent to all vertices in $G_{2}$, so
$G_{2}+x$ contains a good cycle, and we are done by Lemma 10. If some interior
block $B_{3}$ of $G_{2}$ is non-Gallai (so contains a good cycle), then each
$x$ in $S$ has a path to $B_{3}$ in $G_{2}$ (and sends at most one edge to
$B_{3}$), so we are done by considering $B_{1}$, $B_{3}$, and a shortest path
between them. Instead, assume that every interior block of $G_{2}$ is Gallai.
Since $G_{2}$ only has two endblocks, some $x\in S$ sends an edge to the
interior block $B_{3}$. Again, $G_{2}+x$ contains a good cycle.

Case 2: $\bm{G_{S}}$ has 0 non-Gallai endblocks.

Case 2.1: $\bm{G_{S}}$ has at least 4 endblocks. As in the proof of Lemma 13,
each endblock sends at least $k-1=3$ edges to $S$. So the number of endblocks
in $G_{S}$ is at most $|S|k/(k-1)=3\cdot 4/3=4$. Suppose that $G_{S}$ has 4
Gallai endblocks. If some endblock is a $K_{3}$, then it sends $S$ at least 4
edges, so $S$ has too many incident edges (as above), a contradiction. Now
$G_{S}$ has only 2 components, and no component is a single endblock;
otherwise, $S$ sends that component at least 4 edges, and $4+3\cdot 3>4|S|$, a
contradiction. So let $B_{1},B_{2}$ be endblocks of $G_{1}$ and let
$B_{3},B_{4}$ be endblocks of $G_{2}$, with
$B_{1},B_{2},B_{3},B_{4}\in\\{K_{2},K_{4}\\}$. Similarly, $S$ sends edges only
to non-cut-vertices of $B_{1},B_{2},B_{3},B_{4}$. This implies that if some
vertex $x\in S$ sends two edges each to $G_{1}$ and $G_{2}$, then $x+G_{1}$
and $x+G_{2}$ each contain a good cycle, and we are done by Lemma 10. That is
because, for each $i\in[2]$, either some endblock of $G_{i}$ is $K_{4}$ or
both endblocks of $G_{i}$ are $K_{2}$ and there is an interior endblock
$B_{5}$ that is irregular. Now by Pigeonhole, some $x$ in $S$ must send two
edges each to $G_{1}$ and $G_{2}$, so we are done.

Case 2.2: $\bm{G_{S}}$ has a component that is neither $\bm{K_{3}}$ nor
$\bm{K_{4}}$. By Case 2.1, $G_{S}$ has at most 3 endblocks. So let $B_{1}$ be
a block of $G_{S}$ that is a whole component of $G_{1}$. If $B_{1}$ is an odd
cycle of length 5 or more, then $B_{1}$ sends $S$ at least 10 edges, and
$G_{S}-B_{1}$ sends $S$ at least $k-1=3$ edges, but $10+3>4|S|=12$, a
contradiction. If $B_{1}=K_{2}$, then every vertex of $S$ is adjacent to all
of $B_{1}$, and some pair of vertices in $S$ is non-adjacent. Thus, $G$
contains a $K_{4}^{+}$, and we are done by Lemma 11.

Instead assume that $B_{1}\in\\{K_{3},K_{4}\\}$. This implies that some vertex
$x\in S$, sends at least 2 edges to $B_{1}$ and is not adjacent to all of
$B_{1}$. If $x$ sends an edge to two endblocks in $G_{2}$, then $G_{2}+x$
contains a good cycle (either some endblock of $G_{2}$ is not $K_{2}$, or else
$G_{2}=P_{3}$, or $G_{2}$ contains an interior block that is not $K_{2}$).
Thus, $x$ sends an edge to at most one endblock of $G_{2}$. So if $G_{2}$
contains two endblocks, call them $B_{2}$ and $B_{3}$, then we may assume that
$x$ sends no edges to $B_{3}$ and that $B_{3}\neq K_{2}$. This implies that
some vertex $y\in S$ sends at least 2 edges to $B_{3}$ and is not adjacent to
all of $B_{3}$, so $B_{3}+y$ contains a good cycle. Now we are done, by
considering the good cycles in $B_{1}+x$ and in $B_{3}+y$. Hence $G_{2}$ has a
single endblock; that is, $G_{2}=B_{2}$. By the previous paragraph, $G_{2}\neq
K_{2}$, a contradiction.

Case 2.3: $\bm{G_{S}}$ has a component that is $\bm{K_{3}}$ or has 3
components. Suppose that $B_{1}=B_{2}=K_{3}$. If some vertex $x\in S$ sends
exactly 2 edges to each $G_{i}$, then each $G_{i}+x$ contains a good cycle, so
we are done by Lemma 10. But such $x$ must exist because (a) each $B_{i}$ gets
3 edges from $S$, (b) $S$ sends out at most 12 edges, and (c) we cannot write
6 as a sum of 3 terms, each 1 or 3. Assume instead that $B_{1}=K_{4}$. If
$G_{S}$ has a third component $G_{3}$, then $G_{3}$ is a single block $B_{3}$,
and counting edges from $S$ shows that $B_{1}=B_{2}=B_{3}=K_{4}$ and $S$ is an
independent set. Now $G$ contains a bipartite theta graph (take 2 vertices in
$S$ and a neighbor of each in each component). Assume instead that $G_{S}$ has
only 2 components.

By symmetry, we assume that $B_{1}=K_{4}$ and $B_{2}=K_{3}$. If some vertex
$x_{i}\in S$ sends two edges to each of $B_{1}$ and $B_{2}$, then we are done;
so assume this does not happen. By symmetry, we assume that
$d_{B_{2}}(x_{1})=3$, $d_{B_{2}}(x_{2})=2$, and $d_{B_{2}}(x_{3})=1$, so
$d_{B_{1}}(x_{1})=d_{B_{1}}(x_{2})=1$ and $d_{B_{1}}(x_{3})=2$; see Figure
8(a). This implies that $x_{2}x_{3}\in E(G)$. But now $x_{2}$ and $x_{3}$ lie
in a 4-cycle with two vertices of $B_{1}$, and they also lie in a 4-cycle with
two vertices of $B_{2}$. The union of these 4-cycles is a bipartite theta
graph; so we are done, by Lemma 9.

$x_{1}$$x_{3}$$x_{2}$$B_{1}$$S$$B_{2}$ (a)

$x_{1}$$x_{3}$$x_{2}$$B_{1}$$S$$B_{2}$ (b)

Figure 8: $S$ and the components of $G_{S}$ when (a) $B_{1}=K_{4}$ and
$B_{2}=K_{3}$, and (b) $B_{1}=B_{2}=K_{4}$.

Case 2.4: $\bm{G_{S}}$ has 2 components and both are $\bm{K_{4}}$. Suppose
that $B_{1}=B_{2}=K_{4}$ (and $G_{S}$ has only two components). Denote $S$ by
$x_{1},x_{2},x_{3}$. By symmetry (and counting edges), we assume that
$d_{B_{1}}(x_{1})=d_{B_{2}}(x_{2})=2$ and
$d_{B_{2}}(x_{1})=d_{B_{1}}(x_{2})=d_{B_{1}}(x_{3})=d_{B_{2}}(x_{3})=1$. This
implies that $x_{1}x_{3},x_{2}x_{3}\in E(G)$ and $x_{1}x_{2}\notin E(G)$; see
Figure 8(b). If $y_{1}$ is a neighbor of $x_{1}$ in $B_{1}$ and $y_{2}$ is a
neighbor of $x_{3}$ in $B_{1}$, then $\\{x_{1},x_{3},y_{1},y_{2}\\}$ induces a
4-cycle in $V(B_{1})\cup S$. Similarly, there exists an induced 4-cycle in
$V(B_{2})\cup S$ that uses edge $x_{2}x_{3}$. Each of these 4-cycles is a good
cycle, and they intersect in a single vertex $x_{3}$. So we are done. ∎

Now we handle the case when $G$ is 3-regular and has connectivity 3, and two
vertices of $G$ have distinct lists.

######  Lemma 15.

Let $G$ be 3-connected and 3-regular, but not $K_{4}$. Let $L$ be a
3-assignment for $G$. If there exist $v,w_{1}\in V(G)$ with $L(w_{1})\neq
L(v)$, then $G$ is $L$-swappable.

###### Proof.

Since $G$ is connected, we assume $vw_{1}\in E(G)$. Since $G$ is not a clique,
$G$ has an $L$-coloring by the list version of Brooks’ Theorem. Thus,
$\mathcal{L}\neq\emptyset$. Denote $N(v)$ by $\\{w_{1},w_{2},w_{3}\\}$. If
possible, also choose $v$ so that $L(w_{2})\neq L(v)$ or $L(w_{3})\neq L(v)$
(or both); this choice is used only once, near the end of the proof. If
$w_{1}w_{2},w_{2}w_{3}\in E(G)$, then $\\{w_{1},w_{3}\\}$ is a vertex cut,
which contradicts that $G$ is 3-connected. Thus, by symmetry,
$\\{w_{1},w_{2},w_{3}\\}$ induces at most one edge.

We note that $G-e$ is degree-choosable for each $e\in E(G)$, as follows.
Assume instead that $G-e$ is a Gallai tree for some $e\in E(G)$. Since $G-e$
is 2-connected, it is is a Gallai block, i.e., a complete graph or an odd
cycle. But this is impossible since $G-e$ is irregular. Thus, $G-e$ is degree-
choosable. By Lemma 6, this implies that $|L(x)\cap L(y)|\geq 2$ for all
$xy\in E(G)$. In particular, $|L(w_{i})\cap L(v)|\geq 2$ for each $i\in[3]$.

Let $\mathcal{A}_{1}:=\cup_{\alpha\in L(w_{1})\cap
L(w_{2})}\mathcal{L}_{w_{1},\alpha}\cap\mathcal{L}_{w_{2},\alpha}$††margin:
$\mathcal{A}_{1}$, $\mathcal{B}_{1}$ ††margin:  $\mathcal{A}_{2}$,
$\mathcal{B}_{2}$ ††margin:  $\mathcal{A}_{3}$, $\mathcal{B}_{3}$ and
$\mathcal{B}_{1}:=\cup_{\alpha\in L(w_{1})\setminus
L(v)}\mathcal{L}_{w_{1},\alpha}$. Define $\mathcal{A}_{2}$, $\mathcal{B}_{2}$,
$\mathcal{A}_{3}$, and $\mathcal{B}_{3}$ analogously, as in Table 1. Let
$\mathcal{A}:=\cup_{i=1}^{3}\mathcal{A}_{i}$ and
$\mathcal{B}:=\cup_{i=1}^{3}\mathcal{B}_{i}$.††margin:  $\mathcal{A}$,
$\mathcal{B}$ Observe that $\mathcal{L}=\mathcal{A}\cup\mathcal{B}$. Moreover,
by Lemma 4, $\mathcal{B}_{1}$ is nonempty and mixes. Recall from above that
$G[w_{1},w_{2},w_{3}]$ has at most one edge.

$\mathcal{A}$ | $\mathcal{B}$
---|---
$\mathcal{A}_{1}:\cup_{\alpha\in L(w_{1})\cap L(w_{2})}\mathcal{L}_{w_{1},\alpha}\cap\mathcal{L}_{w_{2},\alpha}$ | $\mathcal{B}_{1}:\cup_{\alpha\in L(w_{1})\setminus L(v)}\mathcal{L}_{w_{1},\alpha}$
$\mathcal{A}_{2}:\cup_{\alpha\in L(w_{1})\cap L(w_{3})}\mathcal{L}_{w_{1},\alpha}\cap\mathcal{L}_{w_{3},\alpha}$ | $\mathcal{B}_{2}:\cup_{\alpha\in L(w_{2})\setminus L(v)}\mathcal{L}_{w_{2},\alpha}$
$\mathcal{A}_{3}:\cup_{\alpha\in L(w_{2})\cap L(w_{3})}\mathcal{L}_{w_{2},\alpha}\cap\mathcal{L}_{w_{3},\alpha}$ | $\mathcal{B}_{3}:\cup_{\alpha\in L(w_{3})\setminus L(v)}\mathcal{L}_{w_{3},\alpha}$

Table 1: Every $L$-coloring is in $\mathcal{A}$ or $\mathcal{B}$.

To help clarify the arguments in this proof, we will often draw an auxiliary
graph that has a vertex for each $\mathcal{A}_{i}$ and $\mathcal{B}_{j}$ that
is non-empty. (Since $|L(w_{i})\cap L(v)|\geq 2$ for all $i$, we have
$|L(w_{i})\setminus L(v)|\leq 1$. Thus, each nonempty $\mathcal{B}_{j}$
mixes.) If $\mathcal{A}_{i}\cup\mathcal{B}_{j}$ mixes, then we draw an edge
between the vertices $\mathcal{A}_{i}$ and $\mathcal{B}_{j}$. So, to show that
$\mathcal{L}$ mixes, it suffices to show that this auxiliary graph is
connected.

Case 1: $\bm{G[w_{1},w_{2},w_{3}]}$ has one edge. By symmetry between $w_{2}$
and $w_{3}$, assume that $w_{1}w_{3}\notin E(G)$. So either $w_{2}w_{3}\in
E(G)$ or $w_{1}w_{2}\in E(G)$.

First suppose $w_{2}w_{3}\in E(G)$. This implies that
$\mathcal{A}_{3}=\emptyset$. Since $w_{1}w_{2}\notin E(G)$, the sets
$\mathcal{A}_{1}$ and $\mathcal{A}_{2}$ are both nonempty. By Lemma 5(2),
$\mathcal{A}_{1}\cup\mathcal{B}_{1}$ and $\mathcal{A}_{2}\cup\mathcal{B}_{1}$
both mix; see Figure 9a. Moreover, for each $i\in\\{2,3\\}$, if
$\mathcal{B}_{i}$ is nonempty, then $\mathcal{B}_{i}\cup\mathcal{A}_{i-1}$
mixes by Lemma 5(2). So $\mathcal{A}\cup\mathcal{B}$ mixes; that is,
$\mathcal{L}$ mixes.

123$\mathcal{A}_{i}$$\mathcal{B}_{j}$(a)123$\mathcal{A}_{i}$$\mathcal{B}_{j}$(b)123$\mathcal{A}_{i}$$\mathcal{B}_{j}$$\mathcal{L}_{w_{1},b}$(c)
Figure 9: (a) The case that $w_{2}w_{3}\in E(G)$. (b) The case that
$w_{1}w_{2}\in E(G)$ and $\mathcal{B}_{3}\neq\emptyset$. (c) The case that
$w_{1}w_{2}\in E(G)$, $\mathcal{B}_{3}=\emptyset$, and
$\mathcal{B}_{2}\neq\emptyset$.

Instead assume $w_{1}w_{2}\in E(G)$. So $\mathcal{A}_{1}=\emptyset$. Since
$w_{2}w_{3}\notin E(G)$, the sets $\mathcal{A}_{2}$ and $\mathcal{A}_{3}$ are
both nonempty. By Lemma 5(2), $\mathcal{A}_{2}\cup\mathcal{B}_{1}$ mixes. Now
we show that $\mathcal{B}_{2}=\mathcal{B}_{3}=\emptyset$. Suppose first that
$\mathcal{B}_{3}\neq\emptyset$. By Lemma 5(2),
$\mathcal{A}_{2}\cup\mathcal{B}_{3}$ and $\mathcal{A}_{3}\cup\mathcal{B}_{3}$
both mix; see Figure 9b. If $\mathcal{B}_{2}=\emptyset$, then we are done,
since $\mathcal{A}\cup\mathcal{B}$ mixes. So assume
$\mathcal{B}_{2}\neq\emptyset$. Now by Lemma 5(2)
$\mathcal{A}_{3}\cup\mathcal{B}_{2}$ mixes. Thus, $\mathcal{A}\cup\mathcal{B}$
mixes; that is, $\mathcal{L}$ mixes. So we assume $\mathcal{B}_{3}=\emptyset$.

Now suppose that $\mathcal{B}_{2}\neq\emptyset$. By Lemma 5,
$\mathcal{B}_{2}\cup\mathcal{A}_{3}$ mixes. Since $\mathcal{B}_{1}$ and
$\mathcal{B}_{2}$ are nonempty, there exists $\alpha\in L(w_{1})\setminus
L(v)$ and $\beta\in L(w_{2})\setminus L(v)$. If $\alpha\neq\beta$, then
$\mathcal{B}_{1}\cap\mathcal{B}_{2}\neq\emptyset$; thus,
$\mathcal{B}_{1}\cup\mathcal{B}_{2}$ mixes. So $\mathcal{A}\cup\mathcal{B}$
mixes, and we are done. So assume $\alpha=\beta$. If $L(w_{1})=L(w_{2})$, then
there exists $\gamma\in L(v)\setminus(L(w_{1})\cap L(w_{2}))$. By Lemma 4, the
set $\mathcal{L}_{v,\gamma}$ mixes. Moreover,
$\mathcal{B}_{1}\cap\mathcal{L}_{v,\gamma}$ and
$\mathcal{B}_{2}\cap\mathcal{L}_{v,\gamma}$ are both nonempty. Thus,
$\mathcal{B}_{1}\cup\mathcal{L}_{v,\gamma}\cup\mathcal{B}_{2}$ mixes. So
$\mathcal{A}\cup\mathcal{B}$ mixes, and we are done. So assume $L(w_{1})\neq
L(w_{2})$. Pick $a\in L(v)\cap L(w_{1})\cap L(w_{2})$ and $b\in
L(w_{1})\setminus L(w_{2})$ and $c\in L(w_{2})\setminus L(w_{1})$; see Figure
10(a). Note that $\mathcal{L}_{w_{1},b}$ mixes by Lemma 4, and
$\mathcal{B}_{2}\cap\mathcal{L}_{w_{1},b}\neq\emptyset$. So
$\mathcal{B}_{2}\cup\mathcal{L}_{w_{1},b}$ mixes; see Figure 9c. Moreover,
there exists $\varphi\in\mathcal{L}_{w_{1},b}\cap\mathcal{L}_{w_{3},b}$, and
$\varphi$ mixes with $\mathcal{B}_{1}$ by Lemma 5(2). Since
$\varphi\in\mathcal{L}_{w_{1},b}$, the set
$\mathcal{L}_{w_{1},b}\cup\mathcal{B}_{1}$ mixes; hence,
$\mathcal{B}_{1}\cup\mathcal{B}_{2}$ mixes. So $\mathcal{A}\cup\mathcal{B}$
mixes, and we are done. So we instead assume $\mathcal{B}_{2}=\emptyset$.

$v$$w_{1}$$w_{2}$$w_{3}$$abc$$abd$$acd$$abc$ (a)

$v$$w_{1}$$w_{2}$$w_{3}$$abc$$abd$$abc$$abc$ (b)

Figure 10: Two cases when $w_{1}w_{2}\in E(G)$. (a) A 3-assignment for $N[v]$
when $d\in L(w_{1})\cap L(w_{2})$ and $L(w_{1})\neq L(w_{2})$ and
$L(v)=L(w_{3})$. (b) A 3-assignment for $N[v]$ when $L(v)=L(w_{2})=L(w_{3})$.

Now $\mathcal{B}_{2}=\emptyset=\mathcal{B}_{3}$, so $L(w_{2})=L(w_{3})=L(v)$;
see Figure 10(b). From above $\mathcal{A}_{1}=\emptyset$ and
$\mathcal{A}_{2}\cup\mathcal{B}_{1}$ mixes. So it suffices to show that
$\mathcal{A}_{3}$ mixes with $\mathcal{B}_{1}$. By Lemma 4, we know that
$\mathcal{L}_{w_{2},c}$ and $\mathcal{L}_{w_{1},d}$ and $\mathcal{L}_{v,c}$
are nonempty sets that mix. Note that $\mathcal{B}_{1}=\mathcal{L}_{w_{1},d}$.
Since $\mathcal{L}_{w_{1},d}\cap\mathcal{L}_{w_{2},c}\neq\emptyset$, we see
that $\mathcal{L}_{w_{2},c}\cup\mathcal{L}_{w_{1},d}$ mixes. Similarly,
$\mathcal{L}_{w_{1},d}\cap\mathcal{L}_{v,c}\neq\emptyset$, so
$\mathcal{L}_{w_{1},d}\cup\mathcal{L}_{v,c}$ mixes. Finally
$\mathcal{L}_{v,c}\cap\mathcal{L}_{w_{2},\alpha}\cap\mathcal{L}_{w_{3},\alpha}\neq\emptyset$
for each $\alpha\in\\{a,b\\}$. Thus,
$\mathcal{L}_{v,c}\cup\bigcup_{\alpha\in\\{a,b\\}}(\mathcal{L}_{w_{2},\alpha}\cap\mathcal{L}_{w_{3},\alpha})$
mixes. Combining all these observations gives that
$\mathcal{L}_{w_{2},c}\cup\mathcal{L}_{w_{1},d}\cup\mathcal{L}_{v,c}\cup\bigcup_{\alpha\in\\{a,b\\}}(\mathcal{L}_{w_{2},\alpha}\cap\mathcal{L}_{w_{3},\alpha})$
mixes. But this set contains $\mathcal{A}_{3}\cup\mathcal{B}_{1}$, so we are
done.

Case 2: $\bm{G[w_{1},w_{2},w_{3}]}$ has no edges. So
$\mathcal{A}_{1},\mathcal{A}_{2}$, and $\mathcal{A}_{3}$ are all nonempty.
Moreover, $\mathcal{B}_{1}\cup\mathcal{A}_{1}$ and
$\mathcal{B}_{1}\cup\mathcal{A}_{2}$ both mix by Lemma 5(2). If
$\mathcal{B}_{2}\neq\emptyset$, then $\mathcal{B}_{2}\cup\mathcal{A}_{1}$ and
$\mathcal{B}_{2}\cup\mathcal{A}_{3}$ both mix by Lemma 5(2); see Figure 11a.
If, in addition, $\mathcal{B}_{3}=\emptyset$, then
$\mathcal{A}\cup\mathcal{B}_{1}\cup\mathcal{B}_{2}$ mixes, and we are done.
Otherwise, $\mathcal{B}_{3}\neq\emptyset$. So
$\mathcal{B}_{3}\cup\mathcal{A}_{2}$ and $\mathcal{B}_{3}\cup\mathcal{A}_{3}$
both mix by Lemma 5(2). Thus, $\mathcal{A}\cup\mathcal{B}$ mixes, and we are
done. So assume $\mathcal{B}_{2}=\emptyset$; by symmetry, also
$\mathcal{B}_{3}=\emptyset$.

123$\mathcal{A}_{i}$$\mathcal{B}_{j}$(a)123$\mathcal{A}_{i}$$\mathcal{B}_{j}$(b)
Figure 11: Here $G[w_{1},w_{2},w_{3}]$ has no edges. (a) The case that
$\mathcal{B}_{2}\neq\emptyset$. (b) The case that
$\mathcal{B}_{2}=\emptyset=\mathcal{B}_{3}$.

Now it suffices to show that $\mathcal{A}_{3}\cup\mathcal{B}_{1}$ mixes. Fix
$z_{1}$ and $z_{2}$ in $N(w_{1})\setminus\\{v\\}$. By symmetry between $w_{1}$
and $v$, we assume $N(w_{1})$ induces no edges and
$L(w_{1})=L(z_{1})=L(z_{2})$; see Figure 12(a). By Lemma 4,
$\mathcal{L}_{v,c}$ is nonempty and mixes. Now we show that $\mathcal{A}_{3}$
mixes. Form $G^{\prime}$ from $G$ by deleting $v$ then identifying $w_{2}$ and
$w_{3}$. Call the new vertex $w_{23}$. Note that $G^{\prime}$ is 2-connected;
equivalently, $w_{23}$ is not a cut-vertex in $G^{\prime}$. To see this, note
that $\\{w_{2},w_{3}\\}$ is not a vertex cut in $G$, since $G$ is 3-connected.
So $\\{w_{2},w_{3},v\\}$ is not a vertex cut in $G$, since $v$ is a leaf in
$G-\\{w_{2},w_{3}\\}$. But the components of $G-\\{v,w_{2},w_{3}\\}$ are the
same as those of $G^{\prime}-w_{23}$. So $w_{23}$ is not a cut-vertex in
$G^{\prime}$, as desired.

Let $L^{\prime}$ be a 3-assignment for $G^{\prime}$ with
$L^{\prime}(w_{23})=L(w_{2})$ and $L^{\prime}(x)=L(x)$ for all other $x\in
V(G^{\prime})$. Now $G^{\prime}$ is $L^{\prime}$-swappable, by Lemma 3(a) with
$w:=w_{1}$, since $d_{G^{\prime}}(w_{1})=2<3=|L^{\prime}(w_{1})|$. We note
that every coloring $\varphi^{\prime}$ of $G^{\prime}$ can be extended to a
coloring $\varphi$ in $G$ since $|\cup_{x\in N(v)}\varphi^{\prime}(x)|\leq 2$.
Thus, $L^{\prime}$-colorings are in bijection with colorings in
$\mathcal{A}_{3}$. Moreover, every $\alpha,\beta$-swap performed in
$\varphi^{\prime}$ can also be performed in $\varphi$ as follows. If the swap
does not involve $N(v)$, or $\varphi(v)\notin\\{\alpha,\beta\\}$, then we
perform the same swap as in $\varphi^{\prime}$ (possibly a swap at $w_{2}$ and
$w_{3}$ each). If $\varphi(w_{1})=\varphi(w_{2})=\varphi(w_{3})$ or $\beta=d$
(so the swap is at $w_{1}$), then we can recolor $v$ with
$\gamma\notin\\{\alpha,\beta\\}$ then perform the swap. Otherwise, suppose
$\varphi(v)=\alpha$ and (i) $\varphi(w_{1})=\beta$, or (ii)
$\varphi(w_{2})=\varphi(w_{3})=\beta$. In case (i), the swap is valid since
$\\{a,b\\}\in L(v)$, and in case (ii), the swap is valid since
$L(v)=L(w_{2})=L(w_{3})$. Thus, $\mathcal{A}_{3}$ mixes, as claimed.

For every
$\varphi\in\cup_{\gamma\in\\{a,b\\}}\mathcal{L}_{w_{2},\gamma}\cap\mathcal{L}_{w_{3},\gamma}$,
either (i) $\varphi(w_{1})=\varphi(w_{2})=\varphi(w_{3})$, or (ii)
$\varphi(w_{1})=d$, or (iii) $\varphi(v)=c$. In case (i), we have
$\mathcal{A}_{1}\cap\mathcal{A}_{2}\cap\mathcal{A}_{3}\neq\emptyset$, so we
are done. In case (ii), $\varphi\in\mathcal{B}_{1}$; and in case (iii),
$\varphi\in\mathcal{L}_{v,c}$. Thus,
$\mathcal{L}_{w_{2},\gamma}\cap\mathcal{L}_{w_{3},\gamma}$ mixes either with
$\mathcal{B}_{1}$ or $\mathcal{L}_{v,c}$, for each $\gamma\in\\{a,b\\}$. So it
suffices to show that $\mathcal{B}_{1}$ mixes with $\mathcal{L}_{v,c}$. By our
choice of $v$ at the beginning of the proof, there exists $u\in
N(z_{1})\setminus\\{w_{1}\\}$ with $L(u)=L(z_{1})$; otherwise, we would have
chosen $z_{1}$ instead of $v$. Since $G$ is 3-connected, $G-z_{1}-z_{2}$
contains a $u,v$-path $P$. Note that $L(x)\neq L(y)$ for some $x$ and $y$ that
are successive on $P$. By construction, either $x$ or $y$ is not in $N(v)\cup
N(w_{1})$; see Figure 12(b). By symmetry, assume $x\notin N(v)\cup N(w_{1})$.
Since there exists $\gamma\in L(x)\setminus L(y)$, by Lemma 4, the set
$\mathcal{L}_{x,\gamma}$ mixes. Further,
$\mathcal{L}_{x,\gamma}\cap\mathcal{B}_{1}\neq\emptyset$ and
$\mathcal{L}_{x,\gamma}\cap\mathcal{L}_{v,c}\neq\emptyset$; thus,
$\mathcal{B}_{1}\cup\mathcal{L}_{v,c}$ mixes, and we are done. ∎

$v$$w_{1}$$w_{2}$$w_{3}$$z_{1}$$z_{2}$$abc$$abc$$abc$$abd$$abd$$abd$$abd$ (a)

$v$$w_{1}$$w_{2}$$w_{3}$$z_{1}$$z_{2}$$u$$y$$x$$abc$$abc$$abc$$abd$$abd$$abd$$abd$
(b)

Figure 12: (a) A 3-assignment for $N(v)\cup N(w_{1})$ when
$L(w_{1})=L(z_{1})=L(z_{2})$ and $L(v)=L(w_{2})=L(w_{3})$. (b) The first
instance, along a $u,v$-path, of a consecutive pair $x,y$ with distinct lists.

######  Theorem 3.

Let $G$ be $3$-regular with connectivity 3. If $L$ is a 3-assignment for $G$,
then $G$ is $L$-swappable unless either (a) $G=K_{4}$ or (b)
$G=K_{2}\,\square\,K_{3}$ and $L(v)=L(w)$ for all $v,w\in V(G)$.

###### Proof.

Let $L$ be a 3-assignment for $G$. If there exists $v,w\in V(G)$ such that
$L(v)\neq L(w)$, then $G$ is $L$-swappable by Lemma 15 (or Lemma 17 when
$G=K_{4}$)666Although we have not yet proved this lemma, its proof is
independent of the present theorem, so invoking it now is logically
consistent. We make this choice to preserve the narrative flow of Section 4..
Otherwise, $L(v)=L(w)$ for every $v,w\in V(G)$. If $G\neq
K_{2}\,\square\,K_{3}$, then by Theorem A [7], $G$ is $L$-swappable. ∎

######  Lemma 16.

Let $G$ be 4-connected, $k$-regular, but not a clique. Let $L$ be a
$k$-assignment for $G$. If there exist $v,w_{1}\in V(G)$ with $vw_{1}\in E(G)$
and $L(w_{1})\neq L(v)$, then $G$ is $L$-swappable.

###### Proof.

By the list version of Brooks’ Theorem [6], $G$ has an $L$-coloring; that is,
$\mathcal{L}\neq\emptyset$. Denote the neighbors of $v$ by
$w_{1},\ldots,w_{k}$. By Lemma 4, for each $i\in[k]$ and each $\alpha\in
L(w_{i})\setminus L(v)$, the set $\mathcal{L}_{w_{i},\alpha}$ mixes. By Lemma
5(2), for all distinct $j,\ell\in[k]$ and each $\beta\in L(w_{j})\cap
L(w_{\ell})$, the set
$\mathcal{L}_{w_{j},\beta}\cap\mathcal{L}_{w_{\ell},\beta}$ mixes. Let
$\mathcal{L}_{1}:=\cup_{i\in[k]}\cup_{\alpha\in L(w_{i})\setminus
L(v)}\mathcal{L}_{w_{i},\alpha}$.††margin:  $\mathcal{L}_{1}$,
$\mathcal{L}_{2}$ Let
$\mathcal{L}_{2}:=\cup_{j,\ell\in[k],j\neq\ell}\cup_{\beta\in L(w_{j})\cap
L(w_{\ell})}\mathcal{L}_{w_{j},\beta}\cap\mathcal{L}_{w_{\ell},\beta}$. By
Pigeonhole, for every $\varphi\in\mathcal{L}$, either
$\varphi\in\mathcal{L}_{1}$ or $\varphi\in\mathcal{L}_{2}$, or both. So
$\mathcal{L}=\mathcal{L}_{1}\cup\mathcal{L}_{2}$.

We will often want to $L$-color a small set of vertices, $S$, and show that
our coloring $\varphi$ of $S$ extends to an $L$-coloring of $G$. This is
possible whenever $S\subset N(v)$ and $|S|\leq 3$ and $|(\cup_{x\in
S}\varphi(x))\cap L(v)|<|S|$. After coloring $S$, we greedily color $G-S$ in
order of nonincreasing distance from $v$. This uses that $G-S$ is connected,
since $G$ is 4-connected and $|S|<4$. And the same argument shows that all
such $L$-colorings (with a fixed coloring of $S$) mix.

Case 1: $\bm{|L(w_{1})\setminus L(v)|\geq 2}$. Note, for each $\alpha\in
L(w_{1})\setminus L(v)$, that $\mathcal{L}_{w_{1},\alpha}\neq\emptyset$.
Further, $\cup_{\alpha\in L(w_{1})\setminus L(v)}\mathcal{L}_{w_{1},\alpha}$
mixes, by Lemma 4. Suppose there exists $i\in[k]\setminus\\{1\\}$ with
$L(w_{i})\setminus L(v)\neq\emptyset$. Similar to above, $\cup_{\beta\in
L(w_{i})\setminus L(v)}\mathcal{L}_{w_{i},\beta}$ mixes. Further, given
$\beta\in L(w_{i})\setminus L(v)$, there exists $\alpha\in L(w_{1})\setminus
L(v)$ such that $\alpha\neq\beta$. Since
$\mathcal{L}_{w_{1},\alpha}\cap\mathcal{L}_{w_{i},\beta}\neq\emptyset$, we see
that $\mathcal{L}_{1}$ mixes.

Fix $i,j\in[k]$ with $w_{i}w_{j}\notin E(G)$ and $L(w_{i})\cap
L(w_{j})\neq\emptyset$; fix $\alpha\in L(w_{i})\cap L(w_{j})$. Recall that
$\mathcal{L}_{w_{i},\alpha}\cap\mathcal{L}_{w_{j},\alpha}$ mixes, by Lemma
5(1). Suppose that $i,j\in[k]\setminus\\{1\\}$. Fix $\alpha\in L(w_{i})\cap
L(w_{j})$. Now there exists $\beta\in
L(w_{1})\setminus(L(v)\cup\\{\alpha\\})$. Thus, there exists an $L$-coloring
$\varphi$ with $\varphi(w_{i})=\varphi(w_{j})=\alpha$ and
$\varphi(w_{1})=\beta$, by the remark before Case 1. Note that
$\varphi\in\mathcal{L}_{w_{1},\beta}\cap(\mathcal{L}_{w_{i},\alpha}\cap\mathcal{L}_{w_{j},\alpha})$.
Thus, $\mathcal{L}_{w_{i},\alpha}\cap\mathcal{L}_{w_{j},\alpha}$ mixes with
$\mathcal{L}_{1}$ for each such choice of $i,j$, and $\alpha\in L(w_{i})\cap
L(w_{j})$.

Finally, suppose there exists $i\in[k]\setminus\\{1\\}$ with $\alpha\in
L(w_{1})\cap L(w_{i})$ and $w_{1}w_{i}\notin E(G)$. Let
$G^{\prime}:=G-vw_{1}$. Let $L^{\prime}(w_{i}):=\\{\alpha\\}$,
$L^{\prime}(w_{1})=\\{\alpha\\}\cup(L(w_{1})\setminus L(v))$, and let
$L^{\prime}(x):=L(x)$ for all other $x\in V(G^{\prime})$. Note that
$G^{\prime}$ has an $L^{\prime}$-coloring and all $L^{\prime}$-colorings of
$G^{\prime}$ mix, by Lemma 1. Further, the $L^{\prime}$-colorings
$\varphi^{\prime}$ of $G^{\prime}$ are in bijection with $L$-colorings
$\varphi$ of $G$ with $\varphi(w_{i})=\alpha$ and
$\varphi(w_{1})\in\\{\alpha\\}\cup(L(w_{1})\setminus L(v))$. This latter set
includes a coloring in
$\mathcal{L}_{w_{1},\alpha}\cap\mathcal{L}_{w_{i},\alpha}$ and also a coloring
in $\mathcal{L}_{1}$. Thus, $\mathcal{L}_{1}\cup\mathcal{L}_{2}$ mixes; that
is, $\mathcal{L}$ mixes.

By symmetry among the $w_{i}$’s, we henceforth assume that $|L(w_{i})\setminus
L(v)|\leq 1$ for all $i\in[k]$.

Case 2: $\bm{|L(w_{i})\setminus L(v)|\leq 1}$ for all $\bm{i\in[k]}$ and
$\bm{|(L(w_{1})\cup L(w_{2}))\setminus L(v)|\geq 2}$. As above,
$\cup_{\alpha\in L(w_{i})\setminus L(v)}\mathcal{L}_{w_{i},\alpha}$ mixes, for
each $i\in[k]$, by Lemma 4. By hypothesis, there exist $\alpha\in
L(w_{1})\setminus L(v)$ and $\beta\in L(w_{2})\setminus L(v)$ with
$\alpha\neq\beta$. So there exists
$\varphi\in\mathcal{L}_{w_{1},\alpha}\cap\mathcal{L}_{w_{2},\beta}$. Further,
for every $i\in[k]$ with $L(w_{i})\neq L(v)$, there exists $\gamma\in
L(w_{i})\setminus L(v)$ such that either (a)
$\mathcal{L}_{w_{1},\alpha}\cap\mathcal{L}_{w_{i},\gamma}\neq\emptyset$ (and
$\gamma\neq\alpha$) or (b)
$\mathcal{L}_{w_{2},\beta}\cap\mathcal{L}_{w_{i},\gamma}\neq\emptyset$ (and
$\gamma\neq\beta$). Thus, $\mathcal{L}_{1}$ mixes.

Now instead fix any distinct $i,j\in[k]$ with $w_{i}w_{j}\notin E(G)$. For
each $\alpha\in L(w_{i})\cap L(w_{j})$, recall that
$\mathcal{L}_{w_{i},\alpha}\cap\mathcal{L}_{w_{j},\alpha}$ mixes by Lemma
5(1). For each such $i,j$ there exists $\alpha\in L(w_{i})\cap L(w_{j})$ and
such a coloring $\varphi$ either with $\varphi(w_{1})\notin L(v)$ or with
$\varphi(w_{2})\notin L(v)$, unless $\\{i,j\\}=\\{1,2\\}$. However, in this
case, $\bigcup_{\alpha\in L(w_{1})\cap
L(w_{2})}\mathcal{L}_{w_{1},\alpha}\cap\mathcal{L}_{w_{2},\alpha}\cup\bigcup_{\beta\in
L(w_{1})\setminus L(v)}\mathcal{L}_{w_{1},\beta}$ mixes, by Lemma 5(2). Thus,
$\mathcal{L}_{1}\cup\mathcal{L}_{2}$ mixes; that is, $\mathcal{L}$ mixes.

By symmetry among the $w_{i}$’s, we now assume $|(L(w_{i})\cup
L(w_{j}))\setminus L(v)|\leq 1$ for all $i,j\in[k]$.

Case 3: $\bm{|\cup_{i\in[k]}L(w_{i})\setminus L(v)|=1}$. Let $\\{\alpha\\}$
denote $\cup_{i\in[k]}L(w_{i})\setminus L(v)$. Note that
$\mathcal{L}_{w_{h},\alpha}$ mixes whenever $h\in[k]$ and $\alpha\in
L(w_{h})$, by Lemma 4. Since $G$ is not a clique, there exist $i,j\in[k]$ such
that $w_{i}w_{j}\notin E(G)$. For each such $i,j$ and $\beta\in L(w_{i})\cap
L(w_{j})$, the set $\mathcal{L}_{w_{i},\beta}\cap\mathcal{L}_{w_{j},\beta}$
mixes, by Lemma 5(1). Now we show that $\mathcal{L}_{w_{h},\alpha}$ mixes with
$\mathcal{L}_{w_{i},\beta}\cap\mathcal{L}_{w_{j},\beta}$ for all such
$h,i,j,\alpha$, and $\beta$. First suppose that $\alpha\neq\beta$. If
$h\notin\\{i,j\\}$, then there exists an $L$-coloring $\varphi$ with
$\varphi(w_{h})=\alpha$ and $\varphi(w_{i})=\varphi(w_{j})=\beta$. If
$h\in\\{i,j\\}$, then this claimed mixing follows from Lemma 5(2). So assume
instead that $\alpha=\beta$. If $h\in\\{i,j\\}$, then this is trivial, since
$\mathcal{L}_{w_{i},\beta}\cap\mathcal{L}_{w_{j},\beta}\subseteq\mathcal{L}_{w_{h},\alpha}$.
So assume $h\notin\\{i,j\\}$. Pick $\beta^{\prime}\in L(w_{i})\cap
L(w_{j})\setminus\\{\alpha\\}$. There exists an $L$-coloring $\varphi$ with
$\varphi(w_{h})=\alpha$ and $\varphi(w_{i})=\varphi(w_{j})=\beta^{\prime}$.
But now we are again done by Lemma 5(2). More specifically,
$\mathcal{L}_{w_{h},\alpha}$ mixes and $\mathcal{L}_{w_{i},\alpha}$ mixes. By
Lemma 5(2), also
$\mathcal{L}_{w_{i},\beta}\cap(\mathcal{L}_{w_{j},\beta}\cup\mathcal{L}_{w_{j},\alpha})$
mixes. Since
$\mathcal{L}_{w_{i},\alpha}\cap\mathcal{L}_{w_{j},\alpha}\subseteq\mathcal{L}_{w_{i},\alpha}$,
we are done. ∎

The next lemma handles the case that $G=K_{k+1}$. The main ideas in the proof
are similar to those in the previous proof, but the details are a bit
different.

######  Lemma 17.

Let $G=K_{k+1}$, where $k\geq 3$, and let $L$ be a $k$-assignment. If there
exist $v,w\in V(G)$ such that $L(v)\neq L(w)$, then $G$ is $L$-swappable.

###### Proof.

We denote the vertices of $G$ by $v_{1},\ldots,v_{k+1}$, and we consider three
cases.

Case 1: There exist $\bm{i,j\in[k+1]}$ such that $\bm{|L(v_{i})\setminus
L(v_{j})|\geq 2}$. Fix $\varphi\in\mathcal{L}$. By symmetry, assume that $i=1$
and $j=2$. Since $|L(v_{2})|=k$ and $|V(G)|=k+1$, there exists $\ell\in[k+1]$
such that $\varphi(v_{\ell})\notin L(v_{2})$. Let $\alpha:=\varphi(v_{\ell})$.
Let $\mathcal{L}_{1}:=\cup_{\beta\in L(v_{1})\setminus
L(v_{2})}\mathcal{L}_{v_{1},\beta}$. By Lemma 4, we know that
$\mathcal{L}_{v_{\ell},\alpha}$ mixes and also $\mathcal{L}_{1}$ mixes. We
will construct an $L$-coloring $\varphi^{\prime}$ such that
$\varphi^{\prime}\in\mathcal{L}_{1}\cap\mathcal{L}_{v_{\ell},\alpha}$. This
will prove that $\mathcal{L}_{1}$ mixes with $\mathcal{L}_{v_{\ell},\alpha}$.
Since $\varphi\in\mathcal{L}_{v_{\ell},\alpha}$ and $\varphi$ is an arbitrary
$L$-coloring, we conclude that $G$ is $L$-swappable. Let
$\varphi^{\prime}(v_{\ell})=\alpha$, color $v_{1}$ from
$L(v_{1})\setminus(L(v_{2})\cup\\{\beta\\})$, and thereafter color greedily,
finishing with $v_{2}$.

Case 2: There exist distinct $\bm{i,j,\ell\in[k+1]}$ and distinct colors
$\bm{\alpha_{i},\alpha_{j}}$ such that $\bm{\alpha_{i}\in L(v_{i})\setminus
L(v_{\ell})}$ and $\bm{\alpha_{j}\in L(v_{j})\setminus L(v_{\ell})}$. We can
assume that Case 1 does not hold, so $|L(w)\setminus L(x)|\leq 1$ for all
$w,x\in V(G)$. By symmetry, we assume that $i=1$, $j=2$, and $\ell=3$. Let
$\mathcal{L}_{1}:=\mathcal{L}_{v_{1},\alpha_{1}}$ and
$\mathcal{L}_{2}:=\mathcal{L}_{v_{2},\alpha_{2}}$. By Lemma 4, note that
$\mathcal{L}_{1}$ mixes and $\mathcal{L}_{2}$ mixes. We construct
$\varphi^{\prime}\in\mathcal{L}_{1}\cap\mathcal{L}_{2}$. Let
$\varphi^{\prime}(v_{1}):=\alpha_{1}$, let
$\varphi^{\prime}(v_{2}):=\alpha_{2}$, and thereafter color greedily,
finishing with $v_{3}$. Fix an arbitrary $L$-coloring $\varphi$. Now it
suffices to show that either $\varphi$ is $L$-equivalent to some $L$-coloring
in $\mathcal{L}_{1}$ or $\varphi$ is $L$-equivalent to some $L$-coloring in
$\mathcal{L}_{2}$. Since $|L(v_{3})|=k$ and $|V(G)|=k+1$, there exists $h$
such that $\varphi(v_{h})\notin L(v_{3})$. Further, either
$\varphi(v_{h})\neq\alpha_{1}$ or $\varphi(v_{h})\neq\alpha_{2}$; by symmetry,
assume the former. Now, as in the previous case, there exists an $L$-coloring
$\varphi^{\prime}$ such that
$\varphi^{\prime}\in\mathcal{L}_{1}\cap\mathcal{L}_{v_{h},\varphi(v_{h})}$.
Since $\mathcal{L}_{v_{h},\varphi(v_{h})}$ mixes, by Lemma 4, we are done.

Case 3: There exist $\bm{i,j,\ell\in[k+1]}$ with $\bm{i\notin\\{j,\ell\\}}$
and a color $\bm{\alpha}$ such that $\bm{\alpha\in(L(v_{j})\cap
L(v_{\ell}))\setminus L(v_{i})}$. We can assume neither Case 1 nor Case 2
holds. So, $|L(v_{i})\cap L(v_{j})|=|L(v_{i})\cap L(v_{\ell})|=k-1$. If
$j=\ell$, i.e., there is only one vertex $v_{j}$ such that $\alpha\in
L(v_{j})$ (implying that $L(v_{l})=L(v_{i})$ for all
$l\in[k+1]\setminus\\{j\\}$), then every coloring $\varphi$ lies in
$\mathcal{L}_{v_{j},\alpha}$. This is because $|L(v_{i})|=k$ and $|V(G)|=k+1$,
which implies that some vertex (namely $v_{j}$) has $\varphi(v_{j})\notin
L(v_{i})$. By Lemma 4, $L_{v_{j},\alpha}$ mixes. So, we conclude that $G$ is
$L$-swappable. Thus, we assume that $j\neq\ell$.

By symmetry, assume that $i=1,j=2,$ and $\ell=3$. If $L(v_{2})=L(v_{3})$, then
pick $\beta\in L(v_{1})\setminus L(v_{2})$. By Lemma 4, each of
$\mathcal{L}_{v_{1},\beta},\mathcal{L}_{v_{2},\alpha},$ and
$\mathcal{L}_{v_{3},\alpha}$ mixes. Moreover,
$\mathcal{L}_{v_{1},\beta}\cap\mathcal{L}_{v_{2},\alpha}\neq\emptyset$ (color
$v_{1}$ with $\beta$, color $v_{2}$ with $\alpha$, then color greedily,
finishing with $v_{3}$). So, $\mathcal{L}_{v_{1},\beta}$ mixes with
$\mathcal{L}_{v_{2},\alpha}$. By symmetry between $v_{2}$ and $v_{3}$, the set
$\mathcal{L}_{v_{1},\beta}$ also mixes with $\mathcal{L}_{v_{3},\alpha}$.
Further, if $\alpha\in L(v_{h})$ for some $h\in[k+1]\setminus\\{2,3\\}$, then
$\mathcal{L}_{v_{h},\alpha}$ mixes by Lemma 4. And as above,
$\mathcal{L}_{v_{h},\alpha}\cap\mathcal{L}_{v_{1},\beta}\neq\emptyset$, which
implies that $\mathcal{L}_{v_{h},\alpha}$ mixes with
$\mathcal{L}_{v_{1},\beta}$. Since $|L(v_{1})|=k$ and $|V(G)|=k+1$, for every
$L$-coloring $\varphi$ there exists $h\in[k+1]$ such that
$\varphi(v_{h})\notin L(v_{1})$. In particular, $\varphi(v_{h})=\alpha$. So,
$\varphi\in\mathcal{L}_{v_{h},\alpha}$, and we conclude that $G$ is
$L$-swappable. Thus, we assume $L(v_{2})\neq L(v_{3})$.

By symmetry, assume
$L(v_{1})=[k],L(v_{2})=(\\{\alpha\\}\cup[k])\setminus\\{1\\},$ and
$L(v_{3})=\\{\alpha\\}\cup[k-1]$. By Lemma 4, each of
$\mathcal{L}_{v_{1},k},\mathcal{L}_{v_{1},1},\mathcal{L}_{v_{2},\alpha},\mathcal{L}_{v_{2},k},\mathcal{L}_{v_{3},\alpha},$
and $\mathcal{L}_{v_{3},1}$ mixes. Moreover,
$\mathcal{L}_{v_{1},k}\cap\mathcal{L}_{v_{2},\alpha}\neq\emptyset$ (color
greedily, finishing with $v_{3}$). Similarly,
$\mathcal{L}_{v_{1},k}\cap\mathcal{L}_{v_{3},1}\neq\emptyset,\mathcal{L}_{v_{1},1}\cap\mathcal{L}_{v_{2},k}\neq\emptyset,$
and $\mathcal{L}_{v_{1},1}\cap\mathcal{L}_{v_{3},\alpha}\neq\emptyset$. Thus,
$\mathcal{L}_{v_{1},k}$ mixes with each of $\mathcal{L}_{v_{2},\alpha}$ and
$\mathcal{L}_{v_{3},1}$; similarly, $\mathcal{L}_{v_{1},1}$ mixes with each of
$\mathcal{L}_{v_{2},k}$ and $\mathcal{L}_{v_{3},\alpha}$. By coloring
greedily, finishing with $v_{1}$, there exists
$\varphi\in\mathcal{L}_{v_{2},\alpha}\cap\mathcal{L}_{v_{3},2}$. And a
$2,\alpha$-swap in $\varphi$ at $v_{2}$ gives a coloring in
$\mathcal{L}_{v_{3},\alpha}$. Thus, $\mathcal{L}_{v_{2},\alpha}$ mixes with
$\mathcal{L}_{v_{3},\alpha}$. Finally, if $\alpha\in L(v_{l})$ for some
$l\in[k+1]\setminus\\{2,3\\}$, then $\mathcal{L}_{v_{l},\alpha}$ mixes by
Lemma 4. And, $\mathcal{L}_{v_{l},\alpha}$ mixes with $\mathcal{L}_{v_{1},1}$
since $\mathcal{L}_{v_{l},\alpha}\cap\mathcal{L}_{v_{1},1}\neq\emptyset$. As
above, for every $L$-coloring $\varphi$, there exists $h\in[k+1]$ such that
$\varphi(v_{h})=\alpha$. Thus, we conclude that $G$ is $L$-swappable. ∎

######  Lemma 18.

Let $G$ be a 4-connected graph that is $k$-regular, but does not contain an
induced 4-wheel, $W_{4}$, and is not $K_{k+1}$. If $L(v)=[k]$ for all $v\in
V(G)$, then $G$ is $L$-swappable.

###### Proof.

Let $G$ satisfy the hypothesis. Fix an arbitrary vertex $v\in V(G)$ and denote
$N(v)$ by $\\{w_{1},\ldots,w_{k}\\}$. By Pigeonhole, for every
$\varphi\in\mathcal{L}$ there exist distinct $i,j,\alpha\in[k]$ with
$w_{i}w_{j}\notin E(G)$ and $\varphi(w_{i})=\varphi(w_{j})=\alpha$. Since
$L(x)=[k]$ for all $x\in V(G)$, for all distinct $i,j$ such that
$w_{i}w_{j}\notin E(G)$ and all distinct $\alpha,\beta\in[k]$, the sets
$\mathcal{L}_{w_{i},\alpha}\cap\mathcal{L}_{w_{j},\alpha}$ and
$\mathcal{L}_{w_{i},\beta}\cap\mathcal{L}_{w_{j},\beta}$ mix with each other;
we simply use $\alpha,\beta$-swaps at $w_{i}$ and $w_{j}$. So, in this
proof,††margin:  $\mathcal{L}_{i,j}$ let
$\mathcal{L}_{i,j}:=\cup_{\alpha\in[k]}(\mathcal{L}_{w_{i},\alpha}\cap\mathcal{L}_{w_{j},\alpha})$.
For convenience, when $w_{i}w_{j}\in E(G)$, let
$\mathcal{L}_{i,j}:=\emptyset$. So $\mathcal{L}=\cup_{i,j\in[k],i\neq
j}\mathcal{L}_{i,j}$.

By Lemma 5, if $w_{i}w_{j}\notin E(G)$, then $\mathcal{L}_{i,j}$ mixes. Fix
distinct $i,j,\ell\in[k]$ such that $w_{i}w_{j},w_{j}w_{\ell}\notin E(G)$. We
show that $\mathcal{L}_{i,j}$ mixes with $\mathcal{L}_{j,{\ell}}$. Let
$G^{\prime}:=G-vw_{j}$, let $L^{\prime}(w_{i}):=\\{1\\}$,
$L^{\prime}(w_{\ell})=\\{2\\}$, $L^{\prime}(w_{j}):=\\{1,2\\}$, and
$L^{\prime}(x):=[k]$ for all $x\in V(G)-\\{w_{i},w_{j},w_{\ell}\\}$. Let
$G^{\prime\prime}:=G-\\{w_{i},w_{j},w_{\ell}\\}$. Note that $G^{\prime\prime}$
is connected, since $G$ is 4-connected. Let $\sigma^{\prime\prime}$ be a
vertex order of $V(G^{\prime\prime})$ by non-increasing distance from $v$, and
let $\sigma^{\prime}:=w_{i},w_{\ell},w_{j},\sigma^{\prime\prime}$. Now
$\sigma^{\prime}$ shows that $\mathcal{L}^{\prime}$ mixes, since each vertex
$x$ is preceded by fewer than $|L^{\prime}(x)|$ neighbors in
$\sigma^{\prime}$.

Now consider distinct $h,i,j,\ell\in[k]$ such that
$w_{h}w_{i},w_{j}w_{\ell}\notin E(G)$. We must show that $\mathcal{L}_{h,i}$
mixes with $\mathcal{L}_{j,\ell}$. If $w_{h}w_{j}\notin E(G)$, then
$\mathcal{L}_{h,i}$ mixes with $\mathcal{L}_{h,j}$ and $\mathcal{L}_{h,j}$
mixes with $\mathcal{L}_{j,\ell}$, as above, so we are done. Assume instead
that $w_{h}w_{j}\in E(G)$. By symmetry, also
$w_{i}w_{j},w_{i}w_{\ell},w_{\ell}w_{h}\in E(G)$. However, now $G$ contains an
induced 4-wheel, a contradiction. ∎

Now we combine the previous four lemmas to completely handle the 4-connected
case.

######  Theorem 4.

Let $G$ be 4-connected. If $G$ is $k$-regular and not $K_{k+1}$, then $G$ is
$k$-swappable. If $G=K_{k+1}$, $L$ is a $k$-assignment, and $L$ is not
identical everywhere, then $G$ is $L$-swappable.

###### Proof.

If $G$ contains $W_{4}$ as an induced subgraph, then we are done by Lemma 12
and Lemma 7. So assume it does not. Fix a $k$-assignment $L$ for $G$. If there
exist $x,y\in V(G)$ such that $L(x)\neq L(y)$, then $G$ is $L$-swappable, by
Lemma 16 or Lemma 17. So assume instead that $L(x)=L(y)$ for all $x,y\in
V(G)$. By symmetry, we assume that $L(v)=[k]$ for all $v\in V(G)$. Now we are
done by Lemma 18. ∎

## Acknowledgment

Thanks to a referee for carefully reading this manuscript and making numerous
suggestions that helped improve the presentation.

## References

  * [1] M. Bonamy, N. Bousquet, C. Feghali, and M. Johnson.  On a conjecture of Mohar concerning Kempe equivalence of regular graphs.  J. Combin. Theory Ser. B, 135:179–199, 2019, arXiv:1510.06964.
  * [2] M. Bonamy, V. Delecroix, and C. Legrand-Duchesne.  Kempe changes in degenerate graphs.  Dec. 2021, arXiv:2112.02313.
  * [3] D. W. Cranston.  Kempe equivalent list edge-colorings of planar graphs.  Discrete Math, 2023, arXiv:2110.06191.
  * [4] D. W. Cranston and L. Rabern.  Brooks’ theorem and beyond.  J. Graph Theory, 80(3):199--225, 2015, arXiv:1403.0479.
  * [5] Q. Deschamps, C. Feghali, F. Kardos, C. Legrand-Duschene, and T. Pierron.  Strengthening a theorem of meyniel.  SIAM Journal on Discrete Mathematics, 37:332--350, 2023, arXiv:2201.07595.
  * [6] P. Erdős, A. L. Rubin, and H. Taylor.  Choosability in graphs.  In Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (Humboldt State Univ., Arcata, Calif., 1979), Congress. Numer., XXVI, pages 125--157. Utilitas Math., Winnipeg, Man., 1980.
  * [7] C. Feghali, M. Johnson, and D. Paulusma.  Kempe equivalence of colourings of cubic graphs.  European J. Combin., 59:1--10, 2017, arXiv:1503.03430.
  * [8] M. Las Vergnas and H. Meyniel.  Kempe classes and the Hadwiger conjecture.  J. Combin. Theory Ser. B, 31(1):95--104, 1981.
  * [9] H. Meyniel.  Les $5$-colorations d’un graphe planaire forment une classe de commutation unique.  J. Combin. Theory Ser. B, 24(3):251--257, 1978.
  * [10] N. Nishimura.  Introduction to reconfiguration.  Algorithms (Basel), 11(4):Paper No. 52, 25, 2018.
  * [11] J. van den Heuvel.  The complexity of change.  In Surveys in combinatorics 2013, volume 409 of London Math. Soc. Lecture Note Ser., pages 127--160. Cambridge Univ. Press, Cambridge, 2013, arXiv:1312.2816.