# Vizing’s conjecture holds ††thanks: The author is supported by National
Science Center of Poland grant 2019/34/E/ST6/00443.

Jonathan Narboni  CNRS, LaBRI, Université de Bordeaux, France.  Theoretical
Computer Science Department, Faculty of Mathematics and Computer Science,
Jagiellonian University, Kraków, Poland

###### Abstract

In 1964 Vizing proved that starting from any $k$-edge-coloring of a graph $G$
one can reach, using only Kempe swaps, a $(\Delta+1)$-edge-coloring of $G$
where $\Delta$ is the maximum degree of $G$. One year later he conjectured
that one can also reach a $\Delta$-edge-coloring of $G$ if there exists one.
Bonamy et. al proved that the conjecture is true for the case of triangle-free
graphs. In this paper we prove the conjecture for all graphs.

##  1 Introduction

In 1964 Vizing proved that the chromatic index of a graph $G$ (i.e.the minimum
number of colors needed to properly colors the edges of $G$), denoted by
$\chi^{\prime}(G)$, is at most $\Delta(G)+1$ colors, where $\Delta(G)$ is the
maximum degree of $G$.

######  Theorem 1.

Any simple graph $G$ satisfy $\chi^{\prime}(G)\leqslant\Delta(G)+1$.

The proof heavily relies on the use of Kempe changes. Kempe changes were
introduced by Kempe in his unsuccessful attempt to prove the $4$-color
theorem, but it turns out that this concept became one of the most fruitful
tool in graph coloring. Throughout this paper, we only consider proper edge-
colorings, and so we will only write colorings to denote proper edge-
colorings. Given a graph $G$ and a coloring $\beta$, a Kempe chains $C$ is a
maximal bichromatic component (Kempe chains were invented in the context of
vertex-coloring, but the principle remains the same for edge-coloring).
Applying a Kempe swap (or Kempe change) on $C$ consists in switching the two
colors in this component. Since $C$ is maximal, the coloring obtained after
the swap is guaranteed to be a proper coloring, and if $C$ is not the unique
maximal bichromatic component containing these two colors, the coloring
obtained after the swap is a coloring different from $\beta$, as the partition
of the edges is different.

The Kempe swaps induce an equivalence relation on the set of colorings of a
graph $G$; two colorings $\beta$ and $\beta^{\prime}$ are equivalent if one
can find a sequence of Kempe swaps to transform $\beta$ into $\beta^{\prime}$.
In 1964, Vizing actually proved a stronger statement, he proved that any
$k$-coloring of a graph $G$ (with $k>\Delta(G)$) is equivalent to a
$(\Delta(G)+1)$-coloring of $G$.

######  Theorem 2.

Let $G$ be a graph and $\beta$ a $k$-coloring of $G$ (with $k>\Delta(G)$).
Then there exists a $(\Delta(G)+1)$-coloring $\beta^{\prime}$ equivalent to
$\beta$.

Note that some graphs only need $\Delta$ colors to be properly colored. One
year later, Vizing proved that this result is generalizable to multigraphs,
and ask the following question:

######  Question 3.

For any (multi)graph $G$ and for any $k$-coloring $\beta$ of $G$, is there
always an optimal coloring equivalent to $\beta$ ?

Note that both in Theorem 1 and in Question 3 we do not have the choice in the
target coloring. If we can choose a specific target optimal coloring, then the
question can be reformulated as a reconfiguration question.

######  Question 4.

For any (multi)graph $G$ and for any $k$-coloring $\beta$, is any optimal
coloring always equivalent to $\beta$ ?

If true, Question 4 would imply the following conjecture, as it suffices to
take the optimal target coloring as an intermediate between the two non-
optimal colorings.

######  Conjecture 5.

Any two non-optimal colorings are equivalent.

Mohar proved the weaker case where we have one additional color [Moh06].

######  Theorem 6 ([Moh06]).

All $(\chi^{\prime}(G)+2)$-colorings are equivalent.

When considering the stronger case, McDonald & al. proved that the conjecture
is true for graphs with maximum degree $3$ [MMS12], Asratian and Casselgren
proved that it is true for graphs with maximum degree $4$ [AC16], and Bonamy &
al. proved that the conjecture is true for triangle-free graphs. In this
paper, we prove that the conjecture is true for all graphs.

######  Theorem 7.

Let $G$ be a graph, all its $(\chi^{\prime}(G)+1)$-edge colorings are Kempe-
equivalent.

Theorem 7 is a direct consequence of the following Lemma which is the main
result of this paper.

######  Lemma 8.

Let $G$ be a graph, any $(\chi^{\prime}(G)+1)$-coloring of $G$ is equivalent
to any $\chi^{\prime}(G)$-coloring of $G$.

##  2 General setting of the proof

The proof inherits the technical setup of [BDK+21], in this section, we
introduce this setting, and give the general outline of the proof of the main
result.

###  2.1 Reduction to $\chi^{\prime}(G)$-regular graphs

The general setting of the proof follows that of [BDK+21] which itself follows
that of [MMS12] and of [AC16]. We first show that we can reduce the problem to
the class of regular graphs. Indeed, given a graph $G$ and a coloring $\beta$,
we can build a graph $G^{\prime}$ s.t. :

  * •

$G^{\prime}$ is $\chi^{\prime}(G)$-regular,

  * •

the coloring $\beta$ can be completed into a coloring $\beta^{\prime}$ of
$G^{\prime}$, and

  * •

if a coloring $\gamma^{\prime}$ is equivalent to $\beta^{\prime}$ in
$G^{\prime}$, then the restriction of $\gamma^{\prime}$ to $G$ is equivalent
to $\beta$.

To build $G^{\prime}$ we step-by-step build a sequence
$G_{1},\cdots,G_{t}=G^{\prime}$ where at each step,
$\delta(G_{i+1})=\delta(G_{i})+1$ (where $\delta(G_{i})$ is the minimum degree
of $G_{i}$). For any $G_{i}$, the graph $G_{i+1}$ is build as follows:

  * •

take two copies of $G_{i}$, and

  * •

add a matching between a vertex and its copy if this vertex has minimum degree
in $G_{i}$.

It is clear that $G^{\prime}$ is $\chi^{\prime}(G)$-regular, and to extend a
coloring of $G_{i}$ to a coloring of $G_{i+1}$, it suffices to copy the
coloring for each copy of $G_{i}$, and since the edges of the matching connect
two vertices of minimum degree, there will always be an available colors for
those edges. Moreover, a Kempe swap in $G_{i}$ has a natural generalization in
$G_{i+1}$: if a swap in $G_{i}$ corresponds to more than one swap in
$G_{i+1}$, it suffices to apply the swap on all the corresponding components
in $G_{i+1}$. From now on, we will only consider $\chi^{\prime}$-regular
graphs.

Note that colorings in regular graphs are easier to handle as the two
following properties are verified:

  * •

for any $(\Delta(G))$-coloring of a $\chi^{\prime}(G)$-regular graph $G$,
every vertex $v$ is incident to exactly one edge of each color, and each color
class is a perfect matching, and

  * •

for any $(\Delta(G)+1)$-coloring $\alpha$ of a $\chi^{\prime}(G)$-regular
graph $G$, every vertex $v$ is incident to all but one color, we call this
color the missing color at $v$, and denote it by $m_{\alpha}(v)$ (we often
drop the $\alpha$ when the coloring is clear from the context).

From now on, in the rest of the paper, we only consider
$\chi^{\prime}$-regular graphs.

###  2.2 The good the bad and the ugly

The general approach to Theorem 7 is an induction on the chromatic index.
Given a graph $G$, a $\Delta(G)$-coloring $\alpha$ and a
$(\Delta(G)+1)$-coloring $\beta$, our goal is to find a sequence of Kempe
swaps to transform $\beta$ into $\alpha$. To do so, we consider a color class
in $\alpha$, say the edges colored $1$. These edges induce a perfect matching
$M$ in $G$, thus, if we can find a coloring $\beta^{\prime}$ equivalent to
$\beta$ s.t. for any edge $e$,
$\beta^{\prime}(e)=1\Leftrightarrow\alpha(e)=1$, then we can proceed by
induction on $G^{\prime}=G\setminus M$, noting that
$\chi^{\prime}(G^{\prime})=\chi^{\prime}(G)-1$, and that the restrictions of
$\alpha$ and $\beta^{\prime}$ to $G^{\prime}$ only use $\Delta(G)-1$, and
$\Delta(G)$ colors respectively.

So, given a $(\Delta(G)+1)$-coloring $\beta$ of $G$, we can partition the
edges of $G$ into three sets, an edge $e$ is called:

  * •

good, if $e\in M$ and $\beta(e)=1$,

  * •

bad, if $e\in M$ and $\beta(e)\neq 1$,and

  * •

ugly, if $e\not\in M$ and $\beta(e)=1$.

A vertex missing the color $1$ is called a free vertex. Toward contradiction,
we assume that $\beta$ is not equivalent to $\alpha$, and we consider a
$(\Delta(G)+1)$-coloring $\beta^{\prime}$ equivalent to $\beta$ which
minimizes the number of ugly edges among the colorings equivalent to $\beta$
that minimize the number of bad edges, we call minimal such a coloring. Thus,
if we can find a coloring $\beta^{\prime\prime}$ equivalent to
$\beta^{\prime}$ where the number of bad is strictly lower than in
$\beta^{\prime}$, or with the same number of bad edges, and strictly fewer
ugly edges, we get a contradiction.

###  2.3 Fan-like tools

In his proof of 64, Vizing introduce a technical tool to apply Kempe swaps on
an edge-coloring in very controlled way: Vizing’s fans. To define them, we
first need to define an auxiliary digraph. Given a graph $G$, a
$(\Delta(G)+1)$-coloring $\beta$ of $G$ and a vertex $v$, the directed graph
$D_{v}$ is defined as follows:

  * •

the vertex set of $D_{v}$ is the set of edges incident with $v$, and

  * •

we put an arc between two vertices $vv_{1}$ and $vv_{2}$ of $D_{v}$, if the
edge $vv_{2}$ is colored with the missing color at $v_{1}$.

The fan around $v$ starting at the edge $e$, denoted by $X_{v}(e)$, is the
maximal sequence of vertices of $D_{v}$ reachable from the edge $e$. It is
sometime more convenient to speak about the color of the starting edge of a
fan, if $c$ is a color, $X_{v}(c)$ denotes the fan around $v$ starting at the
edge colored $c$ incident with $v$. Note that since the graph $G$ is
$\chi^{\prime}(G)$-regular, each vertex misses exactly one color, and thus, in
the digraph $D_{v}$, each vertex has outdegree at most $1$. Hence a fan
${\mathcal{X}}$ is well-defined and we only have three possibilities for the
fan ${\mathcal{X}}$:

  * •

${\mathcal{X}}$ is a path,

  * •

${\mathcal{X}}$ is a cycle, or

  * •

${\mathcal{X}}$ is a comet (i.e. a path with an additional arc between the
sink and an internal vertex of the path) .

If $X=(vv_{1},\cdots,vv_{k})$ is a fan, $v$ is called the central vertex of
the fan, and $vv_{1}$ and $vv_{k}$ are respectively called the first and the
last edge of the fan (similarly, $v_{1}$ and $v_{k}$ are the first and last
vertex of $X$ respectively).

Given a $(\Delta(G)+1)$-coloring $\beta$ of $G$, and fan
${\mathcal{X}}=(vv_{1},\cdots,vv_{k})$ which is a cycle around a vertex $v$,
where each vertex $v_{i}$ misses the color $i$ (and so each edge $vv_{i}$ is
colored $(i-1)$), we can define the coloring $\beta^{\prime}=X^{-1}(\beta)$ as
follows:

  * •

for any edge $vv_{i}$ not in ${\mathcal{X}}$,
$\beta^{\prime}(vv_{i})=\beta(vv_{i})$, and

  * •

for any edge $vv_{i}$ in ${\mathcal{X}}$, $\beta^{\prime}(vv_{i})=i$ and
$m(v_{i})=i-1$

The coloring ${\mathcal{X}}^{-1}(\beta)$ is called the invert of
${\mathcal{X}}$, and we say that $X$ is invertible if ${\mathcal{X}}$ and
${\mathcal{X}}^{-1}(\beta)$ are equivalent. In this paper, we prove that in
any coloring, any cycle is invertible.

######  Lemma 9.

In any $(\chi^{\prime}(G)+1)$-coloring of a $\chi^{\prime}(G)$-regular graph
$G$, any cycle is invertible.

We prove Lemma 9 in Section 2.4, and prove here Theorem 7. The proof of
Theorem 7 is derived from the proof of Theorem 1.6 in [BDK+21]. We first need
the following results from [BDK+21] and [AC16] which we restate here (in a
slightly different way).

######  Observation 10 ([BDK+21]).

In a minimal coloring, every bad edge is adjacent to an ugly edge.

######  Lemma 11 ([BDK+21]).

In a minimal coloring, any ugly edge $uv$ is such that the fans $X_{v}(uv)$
and $X_{u}(uv)$ are cycles.

######  Lemma 12 ([AC16]).

In a minimal coloring both ends of an ugly edge are adjacent to a free vertex.

We first show that in a minimal coloring, there always exists a bad edge
adjacent to an ugly edge and incident with a free vertex.

######  Lemma 13.

In a minimal coloring, there exists a bad edge adjacent to an ugly edge and
incident with a free vertex.

###### Proof.

Let $\beta$ be a minimal coloring, if there is no bad edge in $\beta$, then
all the edges of $M$ are colored $1$ in $\beta$ as desired. So there exists a
bad edge $e$ in $\beta$, and by Observation 10, $e$ is adjacent to an ugly
edge $e^{\prime}$. By Lemma 12, there exists a free vertex $u$ adjacent to an
end of $e^{\prime}$. As $u$ is a free vertex, $u$ is incident with a bad edge,
we denote by $v$ the neighbor of $u$ such that the edge $uv$ is bad. If $v$ is
a free vertex, then we swap the single edge $uv$ to obtain a coloring with
fewer bad edges, so $v$ is not free, and thus $uv$ is adjacent to an ugly
edge; this concludes the proof. ∎

We are now ready to prove Theorem 7, but we first need some terminology and
notations. Given a coloring $\alpha$, for any pair of colors $a$,$b$, we
denote by $K(a,b)$ the graph induced in $G$ by the edges colored $a$ and $b$.
The Kempe chain involving these two colors and containing the element $x\in
V(G)\cup E(G)$ is denoted by $K_{x}^{\alpha}(a,b)$ (we often drop the $\alpha$
when the coloring is clear form the context). It is important to note that if
$a$, $b$, $c$ and $d$ are $4$ different colors, then swapping a component of
$K(a,b)$ before or after swapping a component of $K(c,d)$ does not change the
coloring obtained after the two swaps.

Note also that in an edge-coloring, any Kempe chain $K(a,b)$ is a connected
bipartite subgraph of maximum degree $2$, hence it is either a path, or an
even cycle. To distinguish the notions of fans that can be paths or cycles,
when a Kempe component $C$ of $K(a,b)$ is a path (respectively an even cycle)
we say that $C$ si a $(a,b)$-bichromatic path (respectively a
$(a,b)$-bichromatic cycle). If $u$ is a vertex missing the color $a$, then
$K_{u}(a,b)$ is a $(a,b)$-bichroamtic path whose ends are $u$ and another
vertex missing either $a$ or $b$.

###### Proof of Theorem 7.

Let $\beta$ be a minimal coloring. By Lemma 13, there exists a bad edge $uv$
such that $u$ is free and $v$ is incident with an ugly edge $vw$. By Lemma 11,
the fans $X_{v}(vw)$ and $X_{w}(vw)$ are both cycles. The vertex $v$ does not
belong to $X_{v}(vw)$, otherwise, by Lemma 9 we invert $X_{v}(vw)$ and obtain
a coloring with strictly fewer bad edges. Hence, the vertex $w$ is missing a
color $c^{\prime}$ different from $c=\beta(uv)$ (otherwise, $X_{v}(vw)$ is a
cycle of size $2$ containing $u$). We now consider the component
$C=K_{w}(c,c^{\prime})$, note that since $w$ is missing the color
$c^{\prime}$, this component is a $(c,c^{\prime})$-bichromatic path. If the
component $C$ does not contain the vertex $v$, then we swap it to obtain a
coloring where $w$ is missing the color of the edge $uv$ and we are done.
Thus, $C$ contains $v$ and we have to distinguish whether $v$ is between $u$
and $w$ in $C$ or $u$ is between $w$ and $v$.

######  Case 13.1 ($u$ is between $w$ and $v$ in $C$).

In this case, by Lemma 9 we can invert $X_{v}(vw)$ to obtain a coloring where
the component $K_{w}(c,c^{\prime})$ is now a $(c,c^{\prime})$-bichromatic
cycle that we swap. In the coloring obtained after the swap, $X_{v}(uv)$ is a
cycle, and so by Lemma 9 we can invert it to obtain a coloring with strictly
fewer bad edges; a contradiction.

######  Case 13.2 ($v$ is between $w$ and $u$ in $C$).

In this case, we consider the cycle $X_{w}(vw)$. If it does not contain the
vertex $u$, we invert it by Lemma 9 and obtain a coloring where $u$ and $v$
are free, so it suffices to swap the edge $uv$ to obtain a coloring with
strictly fewer bad edges. Hence the vertex $u$ belongs to $X_{w}(vw)$. After
inverting this cycle, we obtain a minimal coloring where $uv$ is still bad,
$v$ is free, and $uw$ is ugly (the edge $vw$ is not ugly anymore in this
coloring). By Lemma 11, the fan $X_{u}(uw)$ is a cycle. The situation is now
similar to the previous case: we invert the cycle $X_{u}(uw)$ to obtain a
coloring where the component $K_{w}(c,c^{\prime})$ is a
$(c,c^{\prime})$-bichromatic cycle. After swapping this cycle we obtain a
minimal coloring where $X_{u}(uv)$ is a cycle. After inverting this cycle, we
obtain a coloring with one fewer bad edge; a contradiction.

∎

###  2.4 General outline and notations

The proof is an induction on the size of the cycles. Towards contradiction,
assume that there exist non-invertible cycles. A _minimum_ cycle
${\mathcal{V}}$ is a non-invertible cycle of minimum size (i.e. in any
coloring, any smaller cycle is invertible).

A cycle of size $2$ is clearly invertible as it only consists of a single
Kempe chain composed of exactly two edges: to invert the cycle, it suffices to
apply a Kempe swap on this component; so the size of a minimum cycle is at
least $3$.

We now need some more notations. For any fan
${\mathcal{V}}=(vv_{1},\cdots,vv_{k})$, $V({\mathcal{V}})$ denotes the set of
vertices $\\{v_{1},\cdots v_{k}\\}$, and $E({\mathcal{V}})$ denotes the set of
edges $\\{vv_{1},\cdots vv_{k}\\}$. We denote by $\beta({\mathcal{V}})$ the
set of colors involved in ${\mathcal{V}}$ (i.e.
$\beta({\mathcal{V}})=\beta(E({\mathcal{V}}))\cup m(V({\mathcal{V}}))\cup
m(v)$); if ${\mathcal{V}}$ involves the color $c$, $M(X,c)$ denotes the vertex
of $V({\mathcal{V}})$ missing the color $c$. There is a natural order induced
by a fan on its vertices (respectively on its edges), and if $i<j$ we say that
the vertex $v_{i}$ (respectively the edge $vv_{i}$) is before the vertex
$v_{j}$ (respectively the edge $vv_{j}$). For two vertices $v_{i}$ and $v_{j}$
of ${\mathcal{V}}$ we define the subfan ${\mathcal{V}}_{[v_{1},v_{j}]}$ as the
subsequence $(vv_{i},vv_{i+1},\cdots vv_{j})$. We often write
${\mathcal{V}}_{\geqslant v_{i}}$, ${\mathcal{V}}_{>v_{i}}$,
${\mathcal{V}}_{\leqslant v_{i}}$ and ${\mathcal{V}}_{<v_{i}}$ to respectively
denote the subfans $(v_{i},\cdots v_{k})$, $(v_{i+1},\cdots
v_{k})$,$(v_{1},\cdots,v_{i})$, and $(v_{1},\cdots v_{i-1})$.

If the fan ${\mathcal{V}}$ is a cycle in a coloring $\beta$ means applying a
sequence of Kempe swaps to obtain the coloring $X^{-1}(\beta)$. If
${\mathcal{V}}$ is a fan which is a path, inverting ${\mathcal{V}}$ means
applying a sequence of single-edge Kempe swaps on the edges of ${\mathcal{V}}$
such that the ends of the first edge of ${\mathcal{V}}$ are missing the same
color $\beta(vv_{1})$. Note that we often only partially invert paths, i.e. we
apply a sequence of single-edge Kempe swaps on the edges of the paths until we
reach a coloring with a specific missing color at the central vertex.

A cycle ${\mathcal{V}}=(vv_{1},\cdots,vv_{k})$ is called saturated if for any
$i$, $v_{i}\in K_{v}(m(v),m(v_{i}))$. Lemma 2.3 of [BDK+21], which we restate
here, guarantees that if a cycle is not invertible, then it is saturated.

######  Lemma 14 ([BDK+21]).

Let ${\mathcal{V}}$ be a cycle, if ${\mathcal{V}}$ is not saturated, then
${\mathcal{V}}$ is invertible.

This directly implies the same result for any minimum cycle.

######  Lemma 15.

Any minimum cycle is saturated.

Let $X\subseteq E(G)\cup V(G)$, $\beta$ a coloring and $\beta^{\prime}$ a
coloring obtained from $\beta$ by swapping a component $C$. The component is
called $X$-stable if :

  * •

for any $v\in X$, $m^{\beta}(v)=m^{\beta^{\prime}}(v)$, and

  * •

for any $e\in X$, $\beta(e)=\beta^{\prime}(e)$.

In this case, the coloring $\beta^{\prime}$ is called $X$-identical to
$\beta$.

If $S=(C_{1},\cdots,C_{k})$ is a sequence of swaps to transform a coloring
$\beta$ into a coloring $\beta^{\prime}$ where each $C_{j}$ is a Kempe
component. The sequence $S^{-1}$ is defined a the sequence of swaps
$(C_{k},\cdots,C_{1})$. Such a sequence is called $X$-stable is each $C_{j}$
is $X$-stable.

######  Observation 16.

Let $X\subseteq V(G)\cup E(G)$, and $S$ a sequence of swaps that is
$X$-stable. Then the sequence $S^{-1}$ is also $X$-stable.

If a sequence $S$ is $X$-stable, then the coloring obtained after apply $S$ to
$\beta$ is called $X$-equivalent to $\beta$. Note that the notion of
$X$-equivalence is stronger than the notion of $X$-identity. Since two
colorings $\beta$ and $\beta^{\prime}$ may be $X$-identical but not
$X$-equivalent if there exists a coloring $\beta^{\prime\prime}$ in the
sequence between $\beta$ and $\beta^{\prime}$ that is not $X$-identical to
$\beta$. We first have the following obsevration that we will often use in
this paper.

######  Observation 17.

Let ${\mathcal{X}}$ be a subfan in a coloring $\beta_{0}$, $v$ be a vertex
which is not in $V({\mathcal{X}})$, and $S=(C_{1},\cdots,C_{k})$ be a sequence
of trivial swaps of edges incident with $v$, $(\beta_{1},\cdots,\beta_{k})$ be
the colorings obtained after each swap of $S$. If for any
$i\in\\{0,\cdots,k\\}$, $m^{\beta_{i}}(v)\not\in\beta_{0}({\mathcal{X}})$,
then the sequence $S$ is $({\mathcal{X}})$-stable.

###### Proof.

Otherwise, assume that $\mathcal{S}$ is not ${\mathcal{X}}$-stable. Since the
vertex $v$ is not in $V({\mathcal{X}})$, then no edge of ${\mathcal{X}}$ has
been changed during the sequence of swap. Thus the missing color of a vertex
of ${\mathcal{X}}$ has been changed during the sequence of swaps, we denote by
$x$ the first such vertex. Let $s_{i}$ be the swap that change the color of
the edge $vx$, it means that in the coloring $\beta_{i-1}$ the vertices $v$
and $x$ are missing the same color, so
$m^{\beta_{i-1}}\in\beta_{0}({\mathcal{X}})$; a contradiction. ∎

The following observation gives a relation between $X$-equivalence and
$(G\setminus)$-identity between colorings.

######  Observation 18.

Let $\beta$ be a coloring, $X\subseteq V(G)\cup E(G)$, $\beta_{1}$ a coloring
$X$-equivalent to $\beta$, and $\beta_{2}$ a coloring $(G\setminus
X)$-identical to $\beta_{1}$. Then, there exists a coloring $\beta_{3}$
equivalent to $\beta_{2}$ that is $X$-identical to $\beta_{2}$ and
$(G\setminus X)$-identical to $\beta$.

###### Proof.

Let $S$ be the sequence of swaps that transforms $\beta$ into $\beta_{1}$.
Since $\beta_{1}$ is $X$-equivalent to $\beta$, the sequence $S$ is $X$-stable
and thus $E(S)\cap E(X)=V(S)\cap V(X)=\emptyset$. Since $\beta_{2}$ is
$(G\setminus X)$-identical to $\beta_{1}$, it is $S$-identical to $\beta_{1}$.
So applying $S^{-1}$ to $\beta_{2}$ is well-defined and gives a coloring
$\beta_{3}$ $S$-identical to $\beta$. We first prove that $\beta_{3}$ is
$(G\setminus X)$-identical to $\beta$. The coloring $\beta_{1}$ is
$(G\setminus S)$-identical to the coloring $\beta$ by definition of $S$, and
the coloring $\beta_{2}$ is $(G\setminus X)$-identical to $\beta_{1}$, so the
coloring $\beta_{2}$ is $(G\setminus(X\cup S))$-identical to $\beta$. Again by
definition of $S^{-1}$ the coloring $\beta_{3}$ is $(G\setminus S)$-identical
to $\beta_{2}$, so it is $(G\setminus(S\cup X))$-identical to $\beta$. Since
the coloring $\beta_{3}$ is also $S$-identical to $\beta$, in total, it is
$(G\setminus X)$-identical to $\beta$.

We now prove that $\beta_{3}$ is $X$-identical to $\beta_{2}$. Since $E(S)\cap
E(X)=V(S)\cap V(X)=\emptyset$, we have that $E(X)\subseteq E(G)\setminus E(S)$
and $V(X)\subseteq V(G)\setminus V(S)$. Moreover, the coloring $\beta_{3}$ is
$(G\setminus S)$-identical to $\beta_{2}$ by definition of $S$, so the
coloring $\beta_{3}$ is $X$-identical to $\beta_{2}$ as desired. ∎

If ${\mathcal{X}}$ is a fan, when two colorings are $(V({\mathcal{X}})\cup
E({\mathcal{X}}))$-identical (respectively $(V({\mathcal{X}})\cup
E({\mathcal{X}}))$-equivalent), we simply write that the two colorings are
${\mathcal{X}}$-identical (respectively ${\mathcal{X}}$-equivalent).
Similarly, if two colorings are $((V(G)\cup E(G))\setminus X)$-identical
(respectively $((V(G)\cup E(G))\setminus X)$-equivalent), we simply write that
the two colorings are $(G\setminus X)$-identical (respectively $(G\setminus
X)$-equivalent).

Remark that if ${\mathcal{V}}$ is a cycle in a coloring $\beta$, then the
coloring ${\mathcal{V}}^{-1}(\beta)$ is $(G\setminus{\mathcal{V}})$-identical
to $\beta$. So from the previous observation we have the following corollary.

######  Corollary 19.

Let ${\mathcal{V}}$ be a cycle in a coloring $\beta$. If there exists a
coloring $\beta^{\prime}$ ${\mathcal{V}}$-equivalent to $\beta$ where
${\mathcal{V}}$ is invertible, then ${\mathcal{V}}$ is invertible in $\beta$.

###### Proof.

Let $\beta^{\prime\prime}={\mathcal{V}}^{-1}(\beta^{\prime})$. The coloring
$\beta^{\prime}$ is ${\mathcal{V}}$-equivalent to $\beta$ and
$\beta^{\prime\prime}$ is $(G\setminus{\mathcal{V}})$-identical to
$\beta^{\prime}$. So by Observation 18 there exists a coloring $\beta_{3}$
that is ${\mathcal{V}}$-identical to $\beta^{\prime\prime}$ and
$(G\setminus{\mathcal{V}})$-identical to $\beta$. So the coloring $\beta_{3}$
is $(G\setminus{\mathcal{V}})$-identical to ${\mathcal{V}}^{-1}(\beta)$.

Moreover, the coloring $\beta^{\prime\prime}$ is ${\mathcal{V}}$-identical to
${\mathcal{V}}^{-1}(\beta)$, so the coloring $\beta_{3}$ is also
${\mathcal{V}}$-identical to ${\mathcal{V}}^{-1}(\beta)$. Therefore we have
$\beta_{3}={\mathcal{V}}^{-1}(\beta)$ as desired. ∎

From the previous corollary, we have the following observation.

######  Observation 20.

Let ${\mathcal{V}}$ be a minimum cycle in coloring $\beta$, and
$\beta^{\prime}$ a coloring ${\mathcal{V}}$-equivalent to $\beta$. Then in the
coloring $\beta^{\prime}$, the sequence ${\mathcal{V}}$ is also a minimuù
cycle such that for any $e\in E({\mathcal{V}})$, $\beta(e)=\beta^{\prime}(e)$,
and for any $v\in V({\mathcal{V}})$, $m^{\beta}(v)=m^{\beta^{\prime}}(v)$.

We often simply say that the cycle ${\mathcal{V}}$ is the same minimum cycle
in the coloring $\beta^{\prime}$.

A cycle ${\mathcal{V}}=(vv_{1},\cdots,vv_{k})$ is called tight if for every
$i$ $v_{i}\in K_{v_{i-1}}(m(v_{i}),m(v_{i-1}))$. A simple observation is that
any minimum cycle ${\mathcal{V}}$ is tight.

######  Observation 21.

Let ${\mathcal{V}}=(vv_{1},\cdots,vv_{k})$ be a minimum cycle in a coloring
$\beta$. Then the cycle ${\mathcal{V}}$ is tight.

###### Proof.

Assume that ${\mathcal{V}}$ is not tight, so there exists $i$ such that
$v_{i}\not\in K_{v_{i-1}}(m(v_{i}),mv_{i-1})$. Without loss of generality, we
assume that $i=2$ and that each $v_{j}$ is missing the color $j$. Note that
this means that $\beta(vv_{2})=1$, $\beta(vv_{3})=2$ and $\beta(vv_{1})=k$.

We swap the component $C_{1,2}=K_{v_{1}}(1,2)$ to obtain a coloring
$\beta^{\prime}$ that is $({\mathcal{V}}\setminus\\{v_{1}\\})$-equivalent to
the coloring $\beta$. Thus each $v_{j}$ is missing the color $j$ except
$v_{1}$ which is now missing the color $2$. So now the fan
${\mathcal{V}}^{\prime}=X_{v}(k)$ is equal to $(vv_{1},vv_{3},\cdots,vv_{k})$,
and thus is a cycle strictly smaller than ${\mathcal{V}}$. Since
${\mathcal{V}}$ is minimum, this cycle is invertible, and we denote by
$\beta^{\prime\prime}$ the coloring obtained after its inversion.

The coloring $\beta^{\prime\prime}$ is
$(G\setminus{\mathcal{V}}^{\prime})$-identical to the coloring
$\beta^{\prime}$, so in particular it is $C_{1,2}$-identical to the coloring
$\beta^{\prime}$. Moreover, the coloring $\beta^{\prime\prime}$ is
$({\mathcal{V}}\setminus\\{vv_{1},vv_{2},v_{2}\\})$-identical to the coloring
${\mathcal{V}}^{-1}(\beta)$, and we have $\beta^{\prime\prime}(vv_{1})=2$,
$\beta^{\prime\prime}(vv_{2})=1$, and $m^{\beta^{\prime\prime}}(v_{2})=2$.

So now in this coloring the component $K_{v_{1}}(1,2)$ is exactly
$C_{1,2}\cup\\{vv_{1},vv_{2}\\}$, and we swap back this component to obtain a
coloring $\beta^{\prime\prime\prime}$. The coloring
$\beta^{\prime\prime\prime}$ is now $C_{1,2}$-identical to $\beta$, and thus
it is $(G\setminus{\mathcal{V}})$-identical to $\beta$. Moreover, it is
$({\mathcal{V}}\setminus\\{vv_{1},vv_{2},v_{2}\\})$-identical to
$\beta^{\prime\prime}$, so it is
$({\mathcal{V}}\setminus\\{vv_{1},vv_{2},v_{2}\\})$-identical to
${\mathcal{V}}^{-1}(\beta)$. Finally, we have
$\beta^{\prime\prime\prime}(vv_{1})=1=m^{\beta}(v_{1})$,
$\beta^{\prime\prime\prime}(vv_{2})=2=m^{\beta}(v_{2})$, and
$m^{\beta^{\prime\prime\prime}}(v_{2})=1=\beta(vv_{2})$, so the coloring
$\beta^{\prime\prime\prime}$ is ${\mathcal{V}}$-identical to
${\mathcal{V}}^{-1}(\beta)$. Since it is also
$(G\setminus{\mathcal{V}})$-identical to $\beta$, we have
$\beta^{\prime\prime\prime}={\mathcal{V}}^{-1}(\beta)$ as desired. ∎

The proof of Lemma 9, is a consequence of the two following Lemmas.

######  Lemma 22.

Let ${\mathcal{V}}$ be a minimum cycle. For any color $c$ different from
$m(v)$, the fan $X_{v}(c)$ is a cycle.

######  Lemma 23.

Let ${\mathcal{X}}$ and ${\mathcal{Y}}$ be two cycles around a vertex $v$. For
any pair of vertices $(z,z^{\prime})$ in
$({\mathcal{V}}\cup{\mathcal{X}}\cup{\mathcal{Y}})^{2}$, the fan
${\mathcal{Z}}=X_{z}(c_{z^{\prime}})$ is a cycle containing $z^{\prime}$.

We prove Lemma 22 in section 2.5, and Lemma 23 in section 5, and prove here
Lemma 9.

###### Proof of Lemma 9.

To prove the Lemma, we prove that the graph $G$ only consists of an even
clique where each vertex misses a different color. This is a contradiction
since in any $(\Delta(G)+1)$-coloring of an even clique, for any color $c$,
the number of vertices missing the color $c$ is always even. By Lemma 22, all
the fans around $v$ are cycles, so each neighbor of $v$ misses a different
color. Moreover, by Lemma 23, there is an edge between each pair of neighbors
of $v$, so $G=N[v]=K_{\Delta(G)+1}$. By construction, $G$ is
$\Delta(G)$-colorable, so $G$ is an even clique and each vertex misses a
different color, this concludes the proof. ∎

###  2.5 Only cycles around $v$: a proof of lemma 22

In this section, we prove Lemma 22. If ${\mathcal{X}}$ and
${\mathcal{X}}^{\prime}$ are two fans, then ${\mathcal{X}}$ and
${\mathcal{X}}^{\prime}$ are called entangled if for any
$c\in\beta({\mathcal{X}})\cap\beta({\mathcal{X}}^{\prime})$,
$M(X,c)=M(X^{\prime},c)$. To prove Lemma 22 we need the two following lemmas.

######  Lemma 24.

Let ${\mathcal{V}}$ be a minimum cycle in a coloring $\beta$ and let $u$ and
$u^{\prime}$ be two vertices of ${\mathcal{V}}$. Then fan
${\mathcal{U}}=X_{u}(m(u^{\prime}))=(uu_{1},\cdots,uu_{l})$ is a cycle
entangled with ${\mathcal{V}}$.

######  Lemma 25.

Let ${\mathcal{V}}$ be a minimum cycle in a coloring $\beta$, $u$ and
$u^{\prime}$ be two vertices of ${\mathcal{V}}$, and
${\mathcal{U}}=X_{u}(m(u^{\prime}))=(uu_{1},\cdots,uu_{l})$. Then for any
$j\leqslant l$, the fan $X_{v}(\beta(uu_{j}))$ is a cycle.

Note that by Lemma 24, we can directly conclude that $N[v]$ is a clique.
Moreover, we directly have the following corollary.

######  Corollary 26.

Let ${\mathcal{V}}=(vv_{1},\cdots,vv_{k})$ be a minimum cycle in a coloring
$\beta$. Then for any $j\leqslant k$, the fan $X_{u}(m(v))$ is a cycle
entangled with ${\mathcal{V}}$.

###### Proof.

Let $j\leqslant k$ and
${\mathcal{U}}=X_{v_{j}}(m(v_{j-1}))=X_{v_{j}}(\beta(vv_{j}))$. Then the first
edge of ${\mathcal{U}}$ is $vv_{j}$, and since $v$ is missing the color
$m(v)$, the second edge of ${\mathcal{U}}$ is colored $m(v)$. By Lemma 24,
${\mathcal{U}}$ is a cycle entanlged with ${\mathcal{V}}$, so since
$X_{u}(m(v))={\mathcal{U}}$, the fan $X_{u}(m(v))$ is a cycle entangled with
${\mathcal{V}}$ as desired. ∎

We prove Lemma 24 in Section 3, Lemma 25 in Section 4, and prove here Lemma
22.

###### Proof of Lemma 22.

Assume that there exists a fan ${\mathcal{W}}=(vw_{1},\cdots,vw_{t})$around
$v$ which does not induce a cycle, we first prove that ${\mathcal{W}}$ is not
a path.

######  Claim 27.

The fan ${\mathcal{W}}$ cannot induce a path.

###### Proof.

Without loss of generality, we assume that the vertex $v$ is missing the color
$1$. Assume that ${\mathcal{W}}$ induces a path, so $m(v)=m(w_{t})=1$. Let
$v^{\prime}\in{\mathcal{V}}$, by Corollary 26, we have that
${\mathcal{U}}=X_{v^{\prime}}(1)$ is a cycle containing $v$ in $\beta$. If we
apply a single-edge Kempe swap on $vw_{t}$, then we obtain a coloring where
$m(w_{t})=m(v)=\beta(vw_{t})$; we denote by $\beta^{\prime}$ this coloring,
and without loss of generality, we assume that $\beta(vw_{t})=2$. Again, by
Corolloary 26, we also have that ${\mathcal{U}}^{\prime}=X_{v^{\prime}}(2)$ is
a cycle containing $v$ in the coloring $\beta^{\prime}$, so
${\mathcal{U}}\cap{\mathcal{U}}^{\prime}\neq\emptyset$, let
$v^{\prime}w^{\prime\prime}$ be the first edge they have in common, and let
$w=M({\mathcal{U}},\beta(v^{\prime}w^{\prime\prime}))$ and
$w^{\prime}=M({\mathcal{U}}^{\prime},\beta(v^{\prime}w^{\prime\prime}))$. We
now have to distinguish whether $v\in\\{w,w^{\prime}\\}$ or not.

######  Case 27.1 ($v\not\in\\{w,w^{\prime}\\}$).

In this case,
$m_{\beta}(w)=m_{\beta^{\prime}}(w)=m_{\beta}(w^{\prime})=m_{\beta^{\prime}}(w^{\prime})$;
we denote by $c$ this color. By Lemma 25, $X_{v}(c)$ is a cycle containing $w$
in $\beta$, and $X_{v}(c)$ is a cycle containing $w^{\prime}$ in
$\beta^{\prime}$, so $w=w^{\prime}$; a contradiction.

######  Case 27.2 ($v\in\\{w,w^{\prime}\\}$).

The case $v=w$ and $v=w^{\prime}$ being symmetrical, we can assume that $v=w$.
In this case, in the coloring $\beta^{\prime}$, $w^{\prime}$ is missing the
color $c_{v}$, but by Lemma 25 $X_{v}(1)$ is a cycle containing $w$ or
${\mathcal{V}}$ is invertible, however, in the coloring $\beta^{\prime}$,
$X_{v}(1)$ induces a path which is a single edge; a contradiction.

∎

Thus the fan ${\mathcal{W}}$ is not a path. Now assume that ${\mathcal{W}}$ is
a comet, then there exists $w$ and $w^{\prime}$ in ${\mathcal{W}}$ which are
missing the same color $c$. At least one of them is not in $K_{v}(1,c)$, the
two cases being symmetrical, we can assume without loss of generality that $w$
is not in $K_{v}(1,c)$. So if we swap the component $K_{w}(1,c)$, we obtain a
coloring where the fan $X_{v}(\beta(vw_{1}))$ is a path; a contradiction, so
${\mathcal{W}}$ is a cycle. ∎

##  3 Fans around ${\mathcal{V}}$: a proof of Lemma 24

In this section, we prove Lemma 24 which will be often used in the proof of
Lemma 25.

###### Proof.

We first prove that the fan ${\mathcal{U}}$ cannot induce a path.

######  Claim 28.

The fan ${\mathcal{U}}$ cannot induce a path.

###### Proof.

Otherwise, assume that the fan ${\mathcal{U}}$ is a path, without loss of
generality, we can assume that ${\mathcal{U}}$ is of minimal length (if
${\mathcal{U}}$ is not minimal, since it is a path, it contains a strictly
smaller path). Thus ${\mathcal{U}}$ contains only one edge colored with a
color in $\beta({\mathcal{V}})\setminus\\{c_{v}\\}$: its first edge. We now
need to distinguish whether $j^{\prime}=j-1$ or not (i.e. whether $u=v_{j}$
and $u^{\prime}=v_{j^{\prime}}$ are consecutive or not in ${\mathcal{V}}$).

######  Case 28.1 ($j^{\prime}=j-1$).

In this case, ${\mathcal{U}}=X_{u}(uv)$, and the edge colored $c_{v}$ incident
with $u$ is just after $uv$ in ${\mathcal{U}}$. As ${\mathcal{U}}$ is a path,
we can invert it until we reach a coloring where $m(u)=m(v)=c_{v}$. Since
${\mathcal{U}}$ is minimal, no edge incident with a vertex of ${\mathcal{V}}$
different from $u$ has been recolored during the inversion. In the coloring
obtained after the inversion, the fan $(vv_{j+1},\cdots,vv_{j}=vu)$ is a path
that we can invert until we reach a coloring where $m(v)=m(v_{j+1})=j$, we
denote by $\beta^{\prime}$ this coloring. Since ${\mathcal{V}}$ was tight in
the coloring $\beta$, in the coloring $\beta^{\prime}$ we have
$C=K_{v_{j-1}}^{\beta^{\prime}}(j,j-1)=K_{v_{j-1}}^{\beta}(j,j-1)\cup\\{vv_{j-1}\\}\setminus\\{vv_{j+1},vv_{j}=vu\\}$,
so we swap this component to obtain a coloring where $m(v)=m(u)=j-1$, then we
swap the edge $uv$ and obtain a coloring where $(uu_{l-1},\cdots,uu_{0})$ is a
path that we invert. In the coloring obtained after the inversion, we have
that the component $K_{v_{j-1}}(j,j-1)$ is exactly $C\cup\\{vv_{j}\\}$, if we
swap this component back we obtain exactly ${\mathcal{V}}^{-1}(\beta)$.

######  Case 28.2 ($j^{\prime}\neq j-1$).

In this case, since ${\mathcal{U}}$ is a path, we can invert it until we reach
a coloring $\beta^{\prime}$ where $m(u)=c_{u^{\prime}}=j^{\prime}$. Note that,
similarly to the previous case, this inversion has not changed the colors of
the edges incident with the vertices of ${\mathcal{V}}$, except those incident
with $u$. We now consider the component $K_{v}(j^{\prime},c_{v})$ (which can
have changed during the inversion of ${\mathcal{U}}$ as we swapped an edge
colored $j^{\prime}$), and we need to distinguish whether or not the vertices
$u^{\prime}$ and $u$ belong to this component; clearly these vertices does not
both belong to this component.

######  Subcase 28.2.1 ($u^{\prime}\not\in K_{v}(j^{\prime},c_{u})$).

In this case, we swap the component $C=K_{u^{\prime}}(j^{\prime},c_{v})$ to
obtain a coloring where$(vv_{j+1},\cdots,vv_{j^{\prime}})$ is a path that we
invert until we reach a coloring where$m(v)=m(v_{j+1})=c_{u}$, we denote by
$\beta^{\prime}$ this coloring. As ${\mathcal{V}}$ was tight in $\beta$, we
have that
$C_{j}=K_{v_{j-1}}^{\beta^{\prime}}(j,j-1)=K_{v_{j-1}}^{\beta}(j,j-1)\setminus\\{vv_{j+1},vv_{j}=vu\\}$,
so we swap this component to obtain a coloring where
$(vv_{j^{\prime}+1},\cdots,vv_{j-1})$ is a path that we invert until we reach
a coloring where $m(v)=m(v_{j^{\prime}+1})=j^{\prime}$. In the coloring
obtained after the inversion, the component $K_{u^{\prime}}(j^{\prime},c_{v})$
is exactly $C\cup\\{vu^{\prime}\\}$, thus we swap it back. Note that as
$|\\{c_{u^{\prime}},c_{v},j,j-1\\}|=4$, we can swap back $C$ before $C_{j}$.
In the coloring obtained after swapping back the component, we have that the
fan $(uu_{l-1},\cdots,uu_{0})$ is a path that we invert. In the coloring
obtained after the inversion, the component $K_{v_{j-1}}(j,j-1)$ is exactly
$C\cup\\{vv_{j-1},vv_{j}=vu\\}$, thus we swap back this component and obtain
exactly ${\mathcal{V}}^{-1}(\beta)$.

So $u^{\prime}$ belongs to the component $K_{v}(j^{\prime},c_{u})$.

######  Subcase 28.2.2 ($u\not\in K_{v}(c_{u^{\prime}},c_{u})$).

In this case, we swap the component $C=K_{u}(j^{\prime},c_{v})$, note that,
from the previous case, neither $v$ nor $u^{\prime}$ belong to this component.
In the coloring obtained after the swap, the fan $(vv_{j+1},\cdots,vv_{j})$ is
a path that we invert until we reach a coloring where $m(v)=m(v_{j+1})=c_{u}$;
we denote by $\beta^{\prime}$ this coloring. As ${\mathcal{V}}$ was tight in
$\beta$, we have that
$C_{j}=K_{v_{j-1}}^{\beta^{\prime}}(j,j-1)=K_{v_{j-1}}^{\beta}(j,j-1)\cup\\{vv_{j-1}\\}\setminus\\{vv_{j+1},vv_{j}=vu\\}$,
so we swap this component to obtain a coloring where $m(v)=m(u)=j-1$, then we
swap the edge $uv$ to obtain a coloring where $K_{u}(c_{u^{\prime}},c_{v})$ is
exactly $C$. Hence we swap back this component, and in the coloring obtained
after the swap, the fan $(uu_{l-1},\cdots,uu_{0})$ is a path that we invert
until we reach a coloring where $m(u)=j$. In this coloring, the component
$K_{v_{j-1}}(j,j-1)$ is exactly $C_{j}\cup\\{vv_{j-1},vv_{j}=vu\\}$, thus we
swap back this component to obtain exactly ${\mathcal{V}}^{-1}(\beta)$.

∎

Before proving that the fan ${\mathcal{U}}$ is not a comet, we prove that
${\mathcal{U}}$ and ${\mathcal{V}}$ are entangled.

######  Claim 29.

The fans ${\mathcal{U}}$ and ${\mathcal{V}}$ are entangled.

###### Proof.

Assume that ${\mathcal{U}}$ and ${\mathcal{V}}$ are not entangled, then there
exist $w=v_{s}\in{\mathcal{V}}$ and
$w^{\prime}=u_{s^{\prime}}\in{\mathcal{U}}$ distinct from $w$ with
$m(w)=m(w^{\prime})=c$. If $m(w)=m(v)=c_{v}$, then, since ${\mathcal{V}}$ is
saturated, $w\in K_{v}(c_{v},c)$, so we swap $K_{w^{\prime}}(c_{v},c)$ to
obtain a coloring where ${\mathcal{V}}$ is still a cycle of the same size, but
where $X_{u}(c_{u^{\prime}})$ is a path, by the previous claim, this is a
contradiction.

So $m(w)\neq m(v)$, and therefore, we successively swap the components
$K_{w^{\prime}}(t,t+1)$ with $t\in(s,\cdots,j)$. Note that this sequence of
swaps has not changed the colors of the edges incident with a vertex of
${\mathcal{V}}$; it can though have changed the colors of the edges of
${\mathcal{U}}$. However, it is guaranteed that in the coloring obtained after
the swaps, there exists a color $c^{\prime}\in\beta({\mathcal{V}})$ such that
$X_{u}(c^{\prime})$ is a path, which is a contradiction by the previous claim.
∎

We now prove that ${\mathcal{U}}$ is not a comet.

######  Claim 30.

The fan ${\mathcal{U}}$ is not a comet.

###### Proof.

Assume that ${\mathcal{U}}$ is a comet, then there exist $w$ and $w^{\prime}$
in ${\mathcal{U}}$ with $m(w)=m(w^{\prime})=c$ and where $w^{\prime}$ is after
$w$ in the sequence. By the previous claim, as ${\mathcal{U}}$ and
${\mathcal{V}}$ are entangled, we have that $c\not\in\beta({\mathcal{V}})$. We
now consider the component $C_{v}=K_{v}(c,c_{v})$. If $w^{\prime}$ is not in
$C_{v}$, then we swap $C_{w^{\prime}}=K_{w^{\prime}}(c,c_{v})$ to obtain a
coloring where $w^{\prime}$ belongs to the fan $X_{u}(c_{u^{\prime}})$ with
$m(w^{\prime})=m(v)$; this contradicts the fact that $X_{u}(c_{u^{\prime}})$
and ${\mathcal{V}}$ are entangled. Note that if $u$ is in $C^{\prime}$, and
$m(v)\in\beta({\mathcal{U}})$, after swapping $C^{\prime}$ the sequence
$X_{u}(c_{u^{\prime}})$ now starts at the edge colored $c$ in $\beta$, but
this does not change the reasoning. So the vertex $w^{\prime}$ belongs to $C$,
and thus the vertex $w$ does not belong to $C_{v}$, so we can swap
$C_{w}=K_{w}(c,c_{v})$ to obtain a coloring where the sequence
$X_{u}(m(u^{\prime}))$ contains $w$ which is missing the color $m(v)$, a
contradiction. Note that if $u\in C_{w}$, then after swapping $C_{w}$, we
obtain a coloring where $w^{\prime}$ comes before $w$ in the fan
$X_{u}(m(u^{\prime}))$. Similarly to the previous case, this does not change
the reasoning. ∎

From the previous claims, the fan ${\mathcal{U}}$ is a cycle entangled with
${\mathcal{V}}$ as desired. ∎

##  4 Cycles around $v$ starting with $u$: a proof ofLemma 25

In this section we prove Lemma 25. To prove the lemma we actually prove a
stronger statement, bu we need first some definitions.

######  Definition 31.

Let $i\geqslant 0$, we define the property $P_{weak}(i)$ as the following: For
any minimum cycle ${\mathcal{V}}$ in a coloring $\beta$, for any pair of
vertices $u$ and $u^{\prime}$ of ${\mathcal{V}}$, let
${\mathcal{U}}=X_{u}(m(u^{\prime}))=(uu_{1},\cdots,uu_{l})$. If
$\beta(uu_{l-i})\neq m(v)$, then $X_{v}(\beta(uu_{l-i})$ is not a path.

######  Definition 32.

Let $i\geqslant 0$, we define the property $P(i)$ as follows:

For any minimum cycle ${\mathcal{V}}$ in a coloring $\beta$, for any pair of
vertices $u$ and $u^{\prime}$ of ${\mathcal{V}}$, let
${\mathcal{U}}=X_{u}(m(u^{\prime}))=(uu_{1},\cdots,uu_{l})$. If
$\beta(uu_{l-i})\neq m(v)$, then the fan $X_{v}(\beta(uu_{l-i})$ is a
saturated cycle containing $u_{l-i-1}$,

Lemma 25 is a direct consequence of the following lemma.

######  Lemma 33.

The property $P(i)$ is true for all $i$.

The proof of the lemma is an induction on $i$. However, before starting to
prove the lemma, we need to introduce the notion of
$({\mathcal{V}},u)$-independent fan for a vertex $u$ of a cycle
${\mathcal{V}}$.

###  4.1 $({\mathcal{V}},u)$-independent fans

Let ${\mathcal{V}}$ be a minimum cycle in a coloring $\beta$, and $u$ a vertex
of ${\mathcal{V}}$. A $({\mathcal{V}},u)$-independent subfan ${\mathcal{X}}$
is a subfan around $v$ such that
$\beta({\mathcal{V}})\cap\beta({\mathcal{X}})=\\{\beta(u)\\}$. We naturally
define a $({\mathcal{V}},u)$-independent path (respectively a
$({\mathcal{V}},u)$-independent cycle) as a $({\mathcal{V}},u)$-independent
subfan that is also a path (respectively a cycle). If $v$ is a vertex not in
${\mathcal{X}}$ missing a color $c$, we say that ${\mathcal{X}}$ avoids $v$ if
the last vertex of ${\mathcal{X}}$ is also missing the color $c$.

We first prove the following.

######  Lemma 34.

Let ${\mathcal{V}}$ be a minimum cycle in a coloring $\beta$, $u$ a vertex of
${\mathcal{V}}$, ${\mathcal{Y}}=(uy_{1},\cdots,uy_{r})$ a
$({\mathcal{V}},u)$-independent subfan avoiding $v$ and $x$ the extremity of
$K_{y_{s}}(m(u),m(v))$ which is not $y_{r}$. Then the fan
$X_{v}(\beta(uy_{1}))$ is a path containing $x$ which is missing the color
$m(v)$.

We decompose the proof into five separate lemmas.

###### Proof of Lemma 34.

Without loss of generality, we assume that the vertices $v$ and $u$ are
respectively missing the colors $1$ and $2$, and that $\beta(uy_{1})=4$. Since
the fan ${\mathcal{V}}$ is a minimum cycle in the coloring $\beta$, it is
saturated by Lemma 15, so $u\in K_{v}(1,2)$ and thus $y_{r}\not\in
K_{v}(1,2)$. We now swap the component $C_{1,2}=K_{y_{r}}(1,2)$ to obtain a
coloring ${\mathcal{V}}$-equivalent to $\beta$, where ${\mathcal{Y}}$ is now a
$({\mathcal{V}},u)$-independent path. By Lemma 39, the fan $X_{v}(4)$ is a
comet containing the other extremity of $K_{y_{r}}(1,2)$ which is $x$. In this
coloring, the vertex $x$ is missing the color $2$, therefore in the coloring
$\beta$, the fan $X_{v}(4)$ is a path containing $x$ which is missing the
color $1$ as desired. ∎

######  Lemma 35.

Let ${\mathcal{X}}=(vv_{1},\cdots,vv_{k})$ be a path of length at least $3$ in
a coloring $\beta$, $u=v_{i}$ for some $i\in[3,k]$,
$u^{\prime\prime}=v_{i-1}$, $u^{\prime}=v_{1}$, and $C$ a
$(\beta(vu),m(u))$-bichromatic path between $u^{\prime\prime}$ and
$u^{\prime}$ that does not contain $v$. Then $\beta$ is equivalent to a
coloring $\beta^{\prime}$ such that:

  * •

$\beta^{\prime}$ is $(G\setminus(C\cup{\mathcal{X}}))$-identical to $\beta$,

  * •

$\beta^{\prime}$ is $({\mathcal{X}}_{\geqslant u})$-identical to $\beta$,

  * •

for any edge $j\in[2,i-1]$, $m^{\beta^{\prime}}(v_{j})=\beta(vv_{j})$,

  * •

$m^{\beta^{\prime}}(u^{\prime})=\beta(vu)$,

  * •

for any edge $j\in[1,i-2]$, $\beta^{\prime}(vv_{j})=m^{\beta}(v_{j})$,

  * •

$\beta^{\prime}(vu^{\prime\prime})=\beta(vu^{\prime})$,

  * •

for any edge $e\in C$:

    * –

if $\beta(e)=\beta(vu)$, then $\beta^{\prime}(e)=m^{\beta}(u)$, and

    * –

if $\beta(e)=m^{\beta}(u)$, then $\beta^{\prime}(e)=\beta(vu)$.

###### Proof.

Without loss of generality, we assume that the vertices $v$ is missing the
color $1$, that the edge $vu^{\prime}$ is colored $2$, and that the edge $vu$
is colored $3$. Note that this means that $m(u^{\prime\prime})=3$. In the
coloring $\beta$, the fan ${\mathcal{X}}$ is a path, so we invert this path,
and denote by $\beta_{2}$ the coloring obtained after the inversion. The
coloring $\beta_{2}$ is $(G\setminus{\mathcal{X}})$-identical to the coloring
$\beta$ so $C$ is still a $(2,3)$-bichromatic path between $u^{\prime}$ and
$u^{\prime\prime}$ that does not contain $v$. Moreover, for any edge
$j\in[1,i]$, $\beta_{2}(vv_{j})=m^{\beta}(v_{j})$ and
$m^{\beta_{2}}(v_{j})=\beta(vv_{j})$. So the coloring $\beta_{2}$ is
$({\mathcal{X}}_{[v_{2},v_{i-2}]}\cup\\{u^{\prime\prime},vu^{\prime}\\})$-identical
to $\beta^{\prime}$. The vertex $u^{\prime}$ is now missing the color $2$, and
the edge $vu^{\prime\prime}$ is now colored $3$. Moreover, the vertex $v$ is
now missing the color $2$, so $K_{v}(2,3)=C\cup\\{vu^{\prime\prime}\\}$. We
now swap this component and denote by $\beta_{3}$ the coloring obtained after
the swap.

The coloring $\beta_{3}$ is $(G\setminus(C\cup{\mathcal{X}}))$-identical to
the coloring $\beta$, so it is $(G\setminus(C\cup{\mathcal{X}}))$-identical to
$\beta^{\prime}$. Moreover, for any edge $e\in C$:

  * •

if $\beta(e)=2$, then $\beta_{3}(e)=3$, and

  * •

if $\beta(e)=3$, then $\beta_{3}(e)=2$.

So the coloring $\beta_{3}$ is also $C$-identical to $\beta^{\prime}$; thus it
is $(G\setminus{\mathcal{X}})$-identical to $\beta^{\prime}$.

The coloring $\beta_{3}$ is
$({\mathcal{X}}_{[v_{2},v_{i-2}]}\cup\\{u^{\prime\prime},vu^{\prime}\\})$-identical
to $\beta_{2}$, so it is
$({\mathcal{X}}_{[v_{2},v_{i-2}]}\cup\\{u^{\prime\prime},vu^{\prime}\\})$-identical
to $\beta^{\prime}$. In the coloring $\beta_{3}$, the edge $vu^{\prime\prime}$
is now colored $2$, and the vertex $u^{\prime}$ is now missing the color $3$.
So the coloring $\beta_{3}$ is also
$(\\{vu^{\prime\prime},u^{\prime}\\})$-identical to $\beta^{\prime}$, and thus
it is ${\mathcal{X}}_{<u}$-identical to $\beta^{\prime}$. In total, the
coloring $\beta_{3}$ is $(G\setminus{\mathcal{X}}_{\geqslant u})$-identical to
the coloring $\beta^{\prime}$.

Finally, the coloring $\beta_{3}$ is ${\mathcal{X}}_{\geqslant u}$-identical
to the coloring $\beta_{2}$ and the verices $v$ and $u$ are both missing the
color $3$. So in the coloring $\beta_{3}$ the fan $X_{v}(1)$ is now a path. We
invert this path and denote by $\beta_{4}$ the coloring obtained after the
inversion. The coloring $\beta_{4}$ is ${\mathcal{X}}_{\geqslant u}$-identical
to the coloring $\beta$, so it is ${\mathcal{X}}_{\geqslant u}$-identical to
the coloring $\beta^{\prime}$. Moreover, the coloring $\beta_{4}$ is also
$(G\setminus{\mathcal{X}}_{\geqslant u})$-identical to the coloring
$\beta_{3}$, so it is $(G\setminus{\mathcal{X}}_{\geqslant u})$-identical to
the coloring $\beta^{\prime}$. In total the coloring $\beta_{4}$ is identical
to the coloring $\beta^{\prime}$ as desired. ∎

######  Lemma 36.

Let ${\mathcal{V}}=(vv_{1},\cdots,vv_{k})$ a cycle of length at least $3$ in a
coloring $\beta$, $u=v_{i}$, $u^{\prime}=v_{i+1}$ and
$u^{\prime\prime}=v_{i-1}$ three consecutive vertices of ${\mathcal{V}}$,
${\mathcal{Y}}=(uy_{1},\cdots,uy_{l})$ a $({\mathcal{V}},u)$-independent path,
$\beta_{{\mathcal{Y}}}={\mathcal{Y}}^{-1}(\beta)$, $C$ a
$(\beta(vu),m(u^{\prime}))$-bichromatic path in the coloring
$\beta_{{\mathcal{Y}}}$ between $u^{\prime\prime}$ and $u^{\prime}$ that does
not contain $v$ nor $u$, $X=E(C)\cup
E({\mathcal{V}})\cup(V({\mathcal{V}})\cup\\{v\\}\setminus\\{u\\})$, and
$\beta^{\prime}_{{\mathcal{Y}}}$ a coloring $X$-equivalent to
$\beta_{{\mathcal{Y}}}$. If there exists a coloring $\beta^{\prime}$
equivalent to $\beta^{\prime}_{{\mathcal{Y}}}$ such that:

  * •

$\beta^{\prime}$ is $(G\setminus X)$-identical to
$\beta^{\prime}_{{\mathcal{Y}}}$,

  * •

$\beta^{\prime}$ is
$({\mathcal{V}}\setminus\\{u^{\prime},vu^{\prime\prime},u,vu\\})$-identical to
${\mathcal{V}}^{-1}(\beta)$,

  * •

$\beta^{\prime}(vu^{\prime\prime})=\beta^{\prime}_{{\mathcal{Y}}}(vu^{\prime})$,

  * •

$\beta^{\prime}(vu)=m^{\beta^{\prime}_{{\mathcal{Y}}}}(u^{\prime\prime})$, and

  * •

$m^{\beta^{\prime}}(u^{\prime})=\beta^{\prime}_{{\mathcal{Y}}}(vu)$,

  * •

for any edge $e\in C$:

    * –

if $\beta^{\prime}_{{\mathcal{Y}}}(e)=\beta(vu)$, then
$\beta^{\prime}(e)=m(u^{\prime})$, and

    * –

if $\beta^{\prime}_{{\mathcal{Y}}}(e)=m(u^{\prime})$, then
$\beta^{\prime}(e)=\beta(vu)$.

Then the cycle ${\mathcal{V}}$ is invertible.

###### Proof.

Let $\gamma={\mathcal{V}}^{-1}(\beta)$. Without loss of generality, we assume
that the vertex $v$ and $u$ are respectively missing the colors $1$ and $2$ in
the coloring $\beta$, and that $\beta(vu)=3$. This means that
$\beta^{\prime}(vu^{\prime\prime})=\beta^{\prime}_{{\mathcal{Y}}}(vu^{\prime})=\beta(vu^{\prime})=m^{\beta}(u)=2$
and
$m^{\beta^{\prime}}(u^{\prime})=\beta^{\prime}_{{\mathcal{Y}}}(vu)=\beta(vu)=m^{\beta}(u^{\prime\prime})=3$.
By definition the coloring $\beta_{{\mathcal{Y}}}$ is
$(G\setminus({\mathcal{Y}}\cup\\{u\\}))$-identical to $\beta$. Since
${\mathcal{Y}}$ is a $({\mathcal{V}},u)$-independent path, we have
$E({\mathcal{Y}})\cap E({\mathcal{V}})=\emptyset$, and $V({\mathcal{Y}})\cap
V({\mathcal{V}})=\emptyset$. So, in particular
$\beta_{{\mathcal{Y}}}(vu)=\beta(vu)=3$. The coloring $\beta^{\prime}$ is
$(\\{vu\\})$-identical to $\beta^{\prime}_{{\mathcal{Y}}}$, so
$\beta^{\prime}(vu)=3$.

Since the coloring $\beta^{\prime}$ is $(G\setminus X)$-identical to
$\beta^{\prime}_{{\mathcal{Y}}}$ and $\beta^{\prime}_{{\mathcal{Y}}}$ is
$X$-equivalent to $\beta_{{\mathcal{Y}}}$, by Observation 18, there exists a
coloring $\beta^{\prime\prime}$ which is $X$-identical to $\beta^{\prime}$ and
$(G\setminus X)$-identical to $\beta_{{\mathcal{Y}}}$.

The coloring $\beta^{\prime\prime}$ is $(G\setminus X)$-identical to
$\beta_{{\mathcal{Y}}}$, so it is
$(G\setminus(X\cup{\mathcal{Y}}\cup\\{u\\}))$-identical to $\beta$. This means
that $\beta^{\prime\prime}$ is $(G\setminus({\mathcal{V}}\cup{\mathcal{Y}}\cup
C))$-identical to $\beta$, and thus it is
$(G\setminus({\mathcal{V}}\cup{\mathcal{Y}}\cup C))$-identical to $\gamma$.
Moreover, $\beta^{\prime\prime}$ is $X$-identical to $\beta^{\prime}$, and
$\beta^{\prime}$ is
$({\mathcal{V}}\setminus(\\{u^{\prime},vu^{\prime\prime},u,vu\\})$-identical
to $\gamma$, so $\beta^{\prime\prime}$ is
$({\mathcal{V}}\setminus(\\{u^{\prime},vu^{\prime\prime},u,vu\\})$-identical
to $\gamma$. In total, the coloring $\beta^{\prime\prime}$ is
$(G\setminus(C\cup{\mathcal{Y}}\cup\\{u^{\prime},vu^{\prime\prime},u,vu\\}))$-identical
to $\gamma$.

In the coloring $\beta_{{\mathcal{Y}}}$, the fan $X_{u}(2)$ is now a path, and
we have $E(X_{u}(2))=E({\mathcal{Y}})$ and $V(X_{u}(2))=V({\mathcal{Y}})$. So
in any coloring $({\mathcal{Y}}\cup\\{u\\})$-identical to
$\beta_{{\mathcal{Y}}}$, the fan $X_{u}(2)$ is a path. The
$\beta^{\prime\prime}$ is $(G\setminus X)$-identical to
$\beta_{{\mathcal{Y}}}$, $E(X)\cap E({\mathcal{Y}})=\emptyset$ and
$V(X)\cap(V({\mathcal{Y}})\cup\\{u\\})=\emptyset$, so $\beta^{\prime\prime}$
is $({\mathcal{Y}}\cup\\{u\\})$-identical to $\beta_{{\mathcal{Y}}}$, and thus
$X^{\beta^{\prime\prime}}_{u}(2)$ is a path that we invert. Let $\beta_{3}$ be
the coloring obtained after the inversion.

By definition of ${\mathcal{Y}}$, the coloring $\beta_{3}$ is
$({\mathcal{Y}}\cup\\{u\\})$-identical to the coloring $\beta$. So it is
${\mathcal{Y}}$-identical to the coloring $\gamma$, and $u$ is now missing the
color $2$. The coloring $\beta_{3}$ is also
$(G\setminus({\mathcal{Y}}\cup\\{u\\}))$-identical to $\beta^{\prime\prime}$,
so it is
$(G\setminus(C\cup\\{u^{\prime},vu^{\prime\prime},u,vu\\}))$-identical to
$\gamma$, and we have
$\beta_{3}(vu^{\prime\prime})=\beta^{\prime\prime}(vu^{\prime\prime})=2$,
$\beta_{3}(vu)=\beta^{\prime\prime}(vu)=3$ and
$m^{\beta_{3}}(u^{\prime})=m^{\beta^{\prime\prime}}(u^{\prime})=3$. Note that
the coloring $\beta_{3}$ is also $C$-identical to the coloring
$\beta^{\prime\prime}$.

The path $C$ is a $(2,3)$-bichromatic path between $u^{\prime\prime}$ and
$u^{\prime}$ and does not contain $v$ nor $u$, so, in the coloring
$\beta_{3}$, we have $K_{u^{\prime}}(2,3)=C\cup\\{vu^{\prime\prime},vu\\}$. We
now swap this component and denote by $\beta_{f}$ the coloring obtained after
the swap. The coloring $\beta_{f}$ is
$(G\setminus(C\cup\\{u^{\prime},vu^{\prime\prime},u,vu\\}))$-identical to the
coloring $\beta_{3}$, so it is
$(G\setminus(C\cup\\{u^{\prime},vu^{\prime\prime},u,vu\\}))$-identical to
$\gamma$. Moreover, since $\beta_{3}$ is $C$-identical to
$\beta^{\prime\prime}$, for any edge $e\in C$:

  * •

if $\beta^{\prime\prime}(e)=\beta_{3}(e)=2$, then $\beta_{f}(e)=3$, and

  * •

if $\beta^{\prime\prime}(e)=\beta_{3}(e)=3$, then $\beta_{f}(e)=2$.

So the coloring $\beta_{f}$ is $C$-identical to the coloring
$\beta_{{\mathcal{Y}}}$, and thus it is $C$-identical to the coloring
$\gamma$. Finally, we have:

  * •

$m^{\beta_{f}}(u)=3=\beta(vu)=m^{\gamma}(u)$,

  * •

$\beta_{f}(vu)=2=m^{\beta}(u)=\gamma(vu)$,

  * •

$m^{\beta_{f}}(u^{\prime})=2=\beta(vu^{\prime})=m^{\gamma}(u^{\prime})$, and

  * •

$\beta_{f}(vu^{\prime\prime})=3=m^{\beta}(u^{\prime\prime})=\gamma(vu^{\prime\prime})$.

Finally we have that $\beta_{f}$ is
$(C\cup\\{u^{\prime},vu^{\prime\prime},u,vu\\})$-identical to $\gamma$, so it
is identical to $\gamma$, and ${\mathcal{V}}$ is invertible as desired. ∎

######  Lemma 37.

Let ${\mathcal{V}}=(vv_{1},\cdots,vv_{i})$ a minimum cycle in a coloring
$\beta$, $u=v_{i}$, $u^{\prime}=v_{1}$ and $u^{\prime\prime}=v_{i-1}$ three
consecutive vertices of ${\mathcal{V}}$, and
${\mathcal{Y}}=(uy_{1},\cdots,uy_{l})$ a $({\mathcal{V}},u)$-independent path,
$C=K_{u^{\prime\prime}}(m(u),m(u^{\prime\prime}))\setminus\\{vu,vu^{\prime}\\}$,
and $X=C\cup
E({\mathcal{V}})\cup(V({\mathcal{V}})\cup\\{v\\}\setminus\\{u\\})$. In any
coloring $\beta^{\prime}_{{\mathcal{Y}}}$ that is $X$-equivalent to the
coloring $\beta_{{\mathcal{Y}}}={\mathcal{Y}}^{-1}(\beta)$, the fan
$X_{v}(m^{\beta}(u))$ is not a path.

###### Proof.

Without loss of generality, we assume that the vertices $v$ and $u$ are
respectively missing the colors $1$ and $2$, and that $\beta(vu)=3$. This
means that $\beta(vu^{\prime})=m^{\beta}(vu)=2$,
$m^{\beta}(u^{\prime\prime})=\beta(vu)=3$, and
$m^{\beta_{{\mathcal{Y}}}}(u)=4$. Assume that
${\mathcal{X}}=X^{\beta^{\prime}_{{\mathcal{Y}}}}_{v}(2)$ is a path. The
vertex $v$ is still missing the color $1$ in the coloring
$\beta_{{\mathcal{Y}}}$ and thus it is still missing $1$ in
$\beta^{\prime}_{{\mathcal{Y}}}$. The coloring $\beta_{{\mathcal{Y}}}$ is
$({\mathcal{V}}\setminus\\{u\\})$-identical to the coloring $\beta$ and so is
the coloring $\beta^{\prime}_{{\mathcal{Y}}}$. So
$\\{u^{\prime},u^{\prime\prime}\\}\subseteq V({\mathcal{X}})$ and
$\beta^{\prime}_{{\mathcal{Y}}}(vu)=\beta(vu)$, so $u\in V({\mathcal{X}})$,
and thus the size of ${\mathcal{X}}$ is at least $3$. Note that this means
that $V({\mathcal{V}})=V({\mathcal{X}}_{\leqslant u})$.

The cycle ${\mathcal{V}}$ is a minimum cycle in $\beta$, so by Observation 21,
it is tight, and in particular, $u\in K_{u^{\prime\prime}}(2,3)$. So the $C$
is a $(2,3)$-bichromatic path between $u^{\prime\prime}$ and $u^{\prime}$ that
does not contain $u$ nor $v$. Since ${\mathcal{Y}}$ is a
$({\mathcal{V}},u)$-independent path, the coloring $\beta_{{\mathcal{Y}}}$ is
$C$-identical to $\beta$. The coloring $\beta^{\prime}_{{\mathcal{Y}}}$ is
$C$-equivalent to $\beta_{{\mathcal{Y}}}$ so $C$ is still the same bichromatic
path in the coloring $\beta^{\prime}_{{\mathcal{Y}}}$.

Since ${\mathcal{X}}$ is a path of path of length at least $3$, by Lemma 35
there exists a coloring $\beta^{\prime}$ such that:

  * •

$\beta^{\prime}$ is $(G\setminus(C\cup{\mathcal{X}}))$-identical to
$\beta^{\prime}_{{\mathcal{Y}}}$,

  * •

$\beta^{\prime}$ is $({\mathcal{X}}_{\geqslant u})$-identical to
$\beta^{\prime}_{{\mathcal{Y}}}$,

  * •

for any edge $j\in[2,i-1]$,
$m^{\beta^{\prime}}(v_{j})=\beta^{\prime}_{{\mathcal{Y}}}(vv_{j})$,

  * •

$m^{\beta^{\prime}}(u^{\prime})=\beta^{\prime}_{{\mathcal{Y}}}(vu)=3$,

  * •

for any edge $j\in[1,i-2]$,
$\beta^{\prime}(vv_{j})=m^{\beta^{\prime}_{{\mathcal{Y}}}}(vv_{j})$,

  * •

$\beta^{\prime}(vu^{\prime\prime})=\beta^{\prime}_{{\mathcal{Y}}}(vu^{\prime})=2$,

  * •

for any edge $e\in C$:

    * –

if $\beta(e)=\beta^{\prime}_{{\mathcal{Y}}}(vu)=3$, then
$\beta^{\prime}(e)=m^{\beta^{\prime}_{{\mathcal{Y}}}}(u)=2$, and

    * –

if $\beta(e)=m^{\beta^{\prime}_{{\mathcal{Y}}}}(u)=2$, then
$\beta^{\prime}(e)=\beta^{\prime}_{{\mathcal{Y}}}(vu)=3$.

The coloring $\beta^{\prime}$ is $(G\setminus(C\cup{\mathcal{X}}))$-identical
to $\beta^{\prime}_{{\mathcal{Y}}}$, and is ${\mathcal{X}}_{\geqslant
u}$-identical to $\beta^{\prime}_{{\mathcal{Y}}}$. So the coloring
$\beta^{\prime}$ is $(G\setminus X)$-identical to
$\beta^{\prime}_{{\mathcal{Y}}}$.

Let $\gamma={\mathcal{V}}^{-1}(\beta)$. For any $j\in[2,i-2]$, we have
$\beta^{\prime}(vv_{j})=m^{\beta^{\prime}_{{\mathcal{Y}}}}(v_{j})=m^{\beta}(v_{j})=\gamma(vv_{j})$,
and
$m^{\beta^{\prime}}(v_{j})=\beta^{\prime}_{{\mathcal{Y}}}(vv_{j})=\beta(vv_{j})=m^{\gamma}(v_{j})$,
so the coloring $\beta^{\prime}$ is
$({\mathcal{V}}\setminus\\{u^{\prime},vu^{\prime},u^{\prime\prime},vu^{\prime\prime},u,vu\\})$-identical
to $\gamma$. Moreover,
$\beta^{\prime}(vu)=m^{\beta_{{\mathcal{Y}}}}(u^{\prime})=m^{\beta}(u^{\prime})=\gamma(vu^{\prime})$
and
$m^{\beta^{\prime}}(u^{\prime\prime})=\beta_{{\mathcal{Y}}}(vu^{\prime\prime})=\beta(vu^{\prime\prime})=m^{\gamma}(u^{\prime\prime})$.
So in total the coloring $\beta^{\prime}$ is
$({\mathcal{V}}\setminus\\{u^{\prime},vu^{\prime\prime},u,vu\\})$-identical to
the coloring $\gamma$.

The coloring $\beta^{\prime}$ is ${\mathcal{X}}_{\geqslant u}$-identical to
$\beta^{\prime}_{{\mathcal{Y}}}$, so in particular,
$\beta^{\prime}(vu)=\beta^{\prime}_{{\mathcal{Y}}}(vu)=m^{\beta^{\prime}_{{\mathcal{Y}}}}(u^{\prime\prime})$.
We also have that
$\beta^{\prime}(vu^{\prime\prime})=2=\beta^{\prime}_{{\mathcal{Y}}}(vu^{\prime})$,
and $m^{\beta^{\prime}}(u^{\prime})=3=\beta^{\prime}_{{\mathcal{Y}}}(vu)$.

Finally, for any edge $e$ in $C$:

  * •

if $\beta_{{\mathcal{Y}}}(e)=\beta(e)=2$, then $\beta^{\prime}(e)=3$, and

  * •

if $\beta_{{\mathcal{Y}}}(e)=\beta(e)=3$, then $\beta^{\prime}(e)=2$.

So by Lemma 36, the cycle ${\mathcal{V}}$ is invertible; a contradiction. ∎

######  Lemma 38.

Let ${\mathcal{V}}=(vv_{1},\cdots,vv_{k})$ be a minimum cycle in a coloring
$\beta$, $u=v_{j}$, $u^{\prime}=v_{j+1}$, and $u^{\prime\prime}=v_{j-1}$ three
consecutive vertices of ${\mathcal{V}}$ and ${\mathcal{Y}}$ a
$({\mathcal{V}},u)$-independent path. Then in the coloring
$\beta_{{\mathcal{Y}}}={\mathcal{Y}}^{-1}(\beta)$, the fan
${\mathcal{X}}=X_{v}(m^{\beta}(u))=(vx_{1},\cdots,vx_{s})$ is a cycle.

###### Proof.

By Lemma 37, the fan ${\mathcal{X}}$ is not a path. To show that it is a
cycle, we prove that ${\mathcal{X}}$ is not a comet. Otherwise, assume that
${\mathcal{X}}$ is a comet, then there exists $i<s$ such that
$m(x_{i})=m(x_{s})$. Without loss of generality, we assume that
$m^{\beta}(v)=1$, $m^{\beta}(u)=\beta(vu^{\prime})=2$,
$\beta(vu)=m^{\beta}(u^{\prime\prime})=3$ and
$m^{\beta_{{\mathcal{Y}}}}(x_{i})=m^{\beta_{{\mathcal{Y}}}}(x_{s})=4$. We now
have to distinguish the cases.

######  Case 38.1 ($4\not\in\beta({\mathcal{V}})$).

In the coloring $\beta$, the fan ${\mathcal{V}}$ is a minimum cycle, so by
Observation 21, it is tight and in particular, $u\in
K_{u^{\prime\prime}}(2,3)$. Let
$C=K_{u^{\prime\prime}}(2,3)\setminus\\{vu^{\prime},vu\\}$. The path $C$ is a
$(2,3)$-bichromatic path between $u^{\prime\prime}$ and $u^{\prime}$ which
does not contain $v$ nor $u$. Since ${\mathcal{Y}}$ is a
$({\mathcal{V}},u)$-independent path, the coloring $\beta_{{\mathcal{Y}}}$ is
$C$-identical to $\beta$, and thus $C$ is still a $(2,3)$-bichromatic path
between $u^{\prime\prime}$ and $u^{\prime}$ which does not contain $u$ nor
$v$. Let $X=C\cup
E({\mathcal{V}})\cup(V({\mathcal{V}})\cup\\{v\\}\setminus\\{u\\})$. We now
consider the components of $K(1,4)$ in the coloring $\beta_{{\mathcal{Y}}}$.
The vertices $x_{i}$ and $x_{s}$ are not both part of $K_{v}(1,4)$. Note that
we may have $x_{i}=u$. If $x_{i}$ does not belong to $K_{v}(1,4)$, then we
swap the component $C_{1,4}=K_{x_{i}}(1,4)$ to obtain a coloring
$\beta^{\prime}$ $X$-equivalent to $\beta_{{\mathcal{Y}}}$ where the fan
$X_{v}(2)$ is now a path. By Lemma 37; this is a contradiction.

So $x_{i}\in K_{v}(1,4)$, and thus $x_{s}\not\in K_{v}(1,4)$. Similarly to the
previous case, we now swap the component $K_{x_{s}}(1,4)$ and obtain a
coloring $X$-equivalent to $\beta_{{\mathcal{Y}}}$ where $X_{v}(2)$ is a path.
By Lemma 37 this is again a contradiction.

######  Case 38.2 ($4\in\beta({\mathcal{V}})$).

In this case, we have that $x_{i}\in V({\mathcal{V}})$. Since ${\mathcal{Y}}$
is a $({\mathcal{V}},u)$-independent path, it does not contain any vertex
missing the color $4$ so $\beta$ is $\\{x_{s}\\}$-identical to
$\beta_{{\mathcal{Y}}}$, and this vertex is still missing the color $4$ in the
coloring $\beta$. Since ${\mathcal{V}}$ is a minimum cycle in the coloring
$\beta$, by Lemma 15 it is saturated, so $x_{i}\in K_{v}(1,4)$, and thus
$x_{s}\not\in K_{v}(1,4)$. We now swap the component $C_{1,4}=K_{x_{s}}(1,4)$,
and denote by $\beta^{\prime}$ the coloring obtained after the swap. The fan
${\mathcal{Y}}$ was a $({\mathcal{V}},u)$-independent path in the coloring
$\beta$, so the coloring $\beta^{\prime}$ is ${\mathcal{Y}}$-equivalent to
$\beta$, and ${\mathcal{Y}}$ is still a $({\mathcal{V}},u)$-independent path
in this coloring. We now invert ${\mathcal{Y}}$ and obtain a coloring
$\beta^{\prime}_{{\mathcal{Y}}}$ which is
$(X^{\beta_{{\mathcal{Y}}}}_{v}(2)\setminus\\{x_{s}\\})$-equivalent to the
coloring $\beta_{{\mathcal{Y}}}$. So now, in the coloring
$\beta^{\prime}_{{\mathcal{Y}}}$, the fan $X_{v}(2)$ is a path, by Lemma 37
this is a contradiction.

∎

######  Lemma 39.

Let ${\mathcal{V}}=(vv_{1},\cdots,vv_{k})$ a minimum cycle in a coloring
$\beta$, $u=v_{j}$ and $u^{\prime}=v_{j+1}$ two consecutive vertices of
${\mathcal{V}}$, ${\mathcal{Y}}=(uy_{1},\cdots,uy_{r})$ a
$({\mathcal{V}},u)$-independent path, and $x$ the extremity of
$K_{y_{r}}(m(u),m(v))$ which is not $y_{r}$. Then the fan
$X_{v}(\beta(uy_{1}))$ is a comet containing $x$ which is missing the color
$m(u)$.

###### Proof.

We assume that ${\mathcal{Y}}$ is of minimum size such that
${\mathcal{X}}=X_{v}(\beta(uy_{1}))$ is not a comet containing $x$ missing the
color $m(u)$. Without loss of generality, we assume that $m(v)=1$,
$m(u)=\beta(vu^{\prime})=2$, $\beta(uv)=m^{\beta}(u^{\prime\prime})=3$, and
$\beta(uy_{1})=4$.

If $|{\mathcal{Y}}|=1$, then ${\mathcal{Y}}$ consists of a single edge. We
swap this edge, and denote by $\beta^{\prime}$ the coloring obtained after the
swap. In the coloring $\beta^{\prime}$, by Lemma 38, the fan $X_{v}(2)$ is a
cycle. In this coloring, the vertex $u$ is missing the color $4$, so
$4\in\beta^{\prime}(X_{v}(2))$. Let
${\mathcal{X}}^{\prime}=(vx_{1},\cdots,vx_{s})$ be the maximal subfan of
$X_{v}(2)$ starting with an edge colored $4$, and not containing any edge of
${\mathcal{V}}$. Note that $E({\mathcal{X}}^{\prime})=E({\mathcal{X}})$ and
$V({\mathcal{X}}^{\prime})=V({\mathcal{X}})$. Note also that we have
$m^{\beta^{\prime}}(x_{s})=2$. The subfan ${\mathcal{X}}^{\prime}$ does not
contain any edge of ${\mathcal{V}}$, thus is does not contain the vertex $u$,
and so it does not contain any vertex missing the color $4$. So the coloring
$\beta$ is ${\mathcal{X}}$-equivalent to the coloring $\beta^{\prime}$, and
thus in the coloring $\beta$, the fan
$X_{v}(4)=(vx_{1},\cdots,vx_{s},vu^{\prime},\cdots,vu)$ is a comet where
$x_{s}$ and $u$ are both missing the color $2$. In the coloring $\beta$, the
cycle ${\mathcal{V}}$ is a minimum cycle, so it is saturated by Lemma 15, and
thus $u\in K_{v}(1,2)$ and $x_{s}\not\in K_{v}(1,2)$. If $x_{s}$ is not in
$K_{y_{r}}(1,2)$, then we swap $C_{1,2}=K_{x_{s}}(1,2)$, to obtain a coloring
$\beta^{\prime\prime}$ which is
$(({\mathcal{X}}\cup{\mathcal{V}}\cup{\mathcal{Y}})\setminus\\{x_{s}\\})$-equivalent
to $\beta$. We now invert the path ${\mathcal{Y}}$, and obtain a coloring
where $X_{v}(2)$ is a path, by Lemma 38 this is a contradiction.

So $|{\mathcal{Y}}|>1$. The size of ${\mathcal{Y}}$ is minimum, so for any
subpath $X_{u}(\beta(uy_{j}))$ of ${\mathcal{Y}}$ with $j>1$, the fan
$X_{v}(\beta(uy_{j}))$ is a comet containing $x$. So the fan $X_{v}(4)$ does
not contain any vertex missing a color in $\beta({\mathcal{Y}})$, otherwise it
would be a comet containing $x$. Hence the coloring
$\beta_{{\mathcal{Y}}}={\mathcal{Y}}^{-1}(\beta)$ is
${\mathcal{X}}$-equivalent to $\beta$. In the coloring
$\beta_{{\mathcal{Y}}}$, the fan $X_{v}(2)$ is a cycle by Lemma 38. Moreover,
it contains the fan ${\mathcal{X}}$ since $u$ is missing the color $4$ in the
coloring $\beta_{{\mathcal{Y}}}$. Therefore, in the coloring $\beta$, the fan
${\mathcal{X}}=(vx_{1},\cdots,vx_{s},vu^{\prime},\cdots,vu)$ is a comet
containing ${\mathcal{V}}$ where $x_{s}$ and $u$ are both missing the color
$2$. Similarly to the previous case, since ${\mathcal{V}}$ is a minimum, it is
saturated by Lemma 15, so $u\in K_{v}(1,2)$, and thus $x_{s}\not\in
K_{v}(1,2)$. If $x_{s}\not\in K_{v}(1,2)$, then we swap
$C_{1,2}=K_{x_{s}}(1,2)$, and obtain a coloring where $X_{v}(4)$ is a path.
This coloring is ${\mathcal{Y}}$-equivalent to $\beta$, and thus if we invert
${\mathcal{Y}}$ we obtain a coloring where $X_{v}(2)$ is a path, a
contradiction by Lemma 38. ∎

In the following section we prove the property $P(0)$.

###  4.2 Proof of $P(0)$

In this section we prove the following lemma.

######  Lemma 40.

The property $P(0)$ is true.

To prove that $P(0)$ is true, we need the following lemma.

######  Lemma 41.

Let ${\mathcal{V}}=(vv_{1},\cdots,vv_{k})$ be a minimum cycle in a coloring
$\beta$, $u=v_{j}$ and $u^{\prime}=v_{j^{\prime}}$ two vertices of
${\mathcal{V}}$. If $uu^{\prime}\in E(G)\cap$, and $\beta(uu^{\prime})\neq
m(v)$, then the fan ${\mathcal{X}}=X_{v}(\beta(uu^{\prime}))$ is a saturated
cycle.

The following lemma is the first step of the proof of Lemma 41.

######  Lemma 42.

Let ${\mathcal{V}}=(vv_{1},\cdots,vv_{k})$ be a minimum cycle in a coloring
$\beta$, $u=v_{j}$ and $u^{\prime}=v_{j^{\prime}}$ two vertices of
${\mathcal{V}}$. If $uu^{\prime}\in E(G)$ and $\beta(uu^{\prime})\neq m(v)$,
then the fan ${\mathcal{X}}=X_{v}(\beta(uu^{\prime}))$ is not a path.

###### Proof.

Otherwise, assume that ${\mathcal{X}}$ is a path. Without loss of generality,
we assume that the vertices $v$, $u$ and $u^{\prime}$ are respectively missing
the colors $1$, $2$ and $3$. Since $\beta(uu^{\prime})\not\in\\{1,2,3\\}$, we
also assume that $\beta(uu^{\prime})=4$. Finally, we assume that
${\mathcal{X}}$ is of length one, indeed if the length of ${\mathcal{X}}$ is
more than one, we invert it until we reach a coloring $\beta^{\prime}$
${\mathcal{V}}$-equivalent to $\beta$ where it has length one without changing
the color of $uu^{\prime}$.

We denote by $x$ the only vertex of ${\mathcal{X}}$, and by $\beta_{2}$ the
coloring obtained after swapping the edge $vx$. The coloring $\beta_{2}$ is
${\mathcal{V}}$-equivalent to $\beta^{\prime}$, so ${\mathcal{V}}$ is the same
minimum cycle in the coloring $\beta_{2}$ by Observation 20. By Lemma 24, the
fans ${\mathcal{U}}=X^{\beta^{\prime}}_{u}(3)=(uu_{1},\cdots,uu_{l})$ and
${\mathcal{U}}^{\prime}=X^{\beta_{2}}_{u^{\prime}}(3)$ are both cycles and
$uu^{\prime}$ is the last edge of both of these cycles; we denote by $w$ the
vertex missing $4$ in ${\mathcal{U}}$. Note that since $\beta(uu^{\prime})=4$,
the vertex $w$ is the vertex $u_{l-1}$, and
${\mathcal{U}}=(uu_{1},\cdots,uw,uu^{\prime})$. We first remark that
$4\not\in\beta({\mathcal{V}})$, otherwise the fan
$E({\mathcal{X}})=E({\mathcal{V}})$, and the fan ${\mathcal{X}}$ is a cycle
and thus is not a path, as desired.

We first prove some basic properties on the fan ${\mathcal{U}}$.

######  Proposition 43.

The fan ${\mathcal{U}}$ contains an edge colored $1$, and there is no edge
colored with a color in $\beta({\mathcal{V}})$ between the edge colored $1$
and the edge colored $4$ in ${\mathcal{U}}$.

###### Proof.

We first prove that there is an edge colored $1$ in the fan ${\mathcal{U}}$.
Assume that ${\mathcal{U}}$ does not contain any edge colored $1$ in the
coloring $\beta^{\prime}$. Since the fan ${\mathcal{U}}$ is a cycle, it means
that it does not contains any vertex missing the color $1$, and in particular
it does not contain $v$. So the coloring $\beta_{2}$ is also
${\mathcal{U}}$-equivalent to the coloring $\beta^{\prime}$. Therefore,
${\mathcal{U}}={\mathcal{U}}^{\prime}$ and ${\mathcal{U}}^{\prime}$ contains
the vertex $w$ that is still missing the color $4$. The fan
${\mathcal{U}}^{\prime}$ is thus not entangled with ${\mathcal{V}}$, by Lemma
24 we have a contradiction.

So the fan ${\mathcal{U}}$ contains an edge colored $1$. Since by Lemma 24,
the fan ${\mathcal{U}}$ is a cycle entangled with ${\mathcal{V}}$, it contains
the vertex $v$ which is missing the color $1$, and thus it contains the edge
$uv$, and also the edge $vv_{j-1}$ (recall that $vv_{j-1}$ is the edge just
before $vu=vv_{j}$ in the sequence ${\mathcal{V}}$). Note that the vertex
$u^{\prime}$ and $v_{j-1}$ may be the same vertex.

We now prove that, in the sequence ${\mathcal{U}}$, there is no edge colored
with a color in $\beta({\mathcal{V}})$ between the edge colored $1$ and the
edge colored $4$. Assume on the contrary that there exists such an edge
$uu_{t}$ colored with a color $c\in\beta({\mathcal{V}})$. Similarly to the
previous proof, this means that in the coloring $\beta_{2}$, the fan
$X_{u}(c)$ is the sequence $(uu_{t},uu_{t+1},\cdots,uw,uu^{\prime})$ with
$m(w)=m(v)=4$. So this fan is not entangled with ${\mathcal{V}}$ and by Lemma
24 we again get a contradiction. ∎

Let $y_{1}$ be the neighbor of $u$ connected to $u$ by the edge colored $1$,
and $y_{2}$ the vertex just after $y_{1}$ in the sequence ${\mathcal{U}}$.
Note that since $\beta^{\prime}(uu^{\prime})\neq 1$, the vertex $y_{1}$ is
different from the vertex $u^{\prime}$ but may be equal to the vertex $w$. In
this case, the vertices $y_{2}$ and $u^{\prime}$ are the same vertex.

######  Proposition 44.

The edge $uy_{1}$ belongs to the component $K_{v}(1,\beta(vu^{\prime}))$.

###### Proof.

Assume that $uy_{1}$ does not belong to $K_{v}(1,\beta(vu^{\prime}))$. If the
edge $vu^{\prime}$ is just after the edge $vu$ in the fan ${\mathcal{V}}$
(i.e. if $j^{\prime}=j+1$), then it means that $\beta(vu^{\prime})=3$, and
since $\beta(uy_{1})=1$, we have that the vertex $u$ does not belong to the
component $K_{v}(1,3)$. So the fan ${\mathcal{V}}$ is not saturated, by Lemma
15 we have a contradiction. So the edge $vu^{\prime}$ is not the edge just
after the edge $vu$ in the fan ${\mathcal{V}}$, and without loss of
generality, we assume that $\beta(vu^{\prime})=5$.

Let $C_{1,5}=K_{y_{1}}(1,5)$, we first prove that the vertex $x$ belongs to
this component. Since the vertex $y_{1}$ is not in $K_{v}(1,5)$, we have that
$K_{v}(1,5)\neq C_{1,5}$. The fan ${\mathcal{V}}$ is a minimum cycle, it is
saturated by Lemma 15, so after swapping $C_{1,5}$, we obtain a coloring
$\beta^{\prime\prime}$ ${\mathcal{V}}$-equivalent to $\beta^{\prime}$. By
Observation 20 the cycle ${\mathcal{V}}$ is the same minimum cycle in this
coloring. In the coloring $\beta^{\prime\prime}$ the edge $uuy_{1}$ is now
colored $5$, and the fan $X_{u}(5)$ still contains the vertex $w$ missing the
color $4$. Moreover, the vertex $x$ is still missing the color $1$, so we swap
the edge $vu$ to obtain a coloring ${\mathcal{V}}$-equivalent to
$\beta^{\prime\prime}$ where $X_{u}(5)$ contains the vertex $w$ which is
missing the color $m(v)=4$. So $X_{u}(5)$ is not entangled with
${\mathcal{V}}$, and by Lemma 24 we have a contradiction.

Therefore, the vertex $x$ belongs to the component $C_{1,5}$. We first swap
the component $C_{1,5}$ and obtain a coloring $\beta^{\prime\prime}$
${\mathcal{V}}$-equivalent to $\beta^{\prime}$. In the coloring
$\beta^{\prime\prime}$, the fan $X_{u}(5)$ now contains the vertex $w$ that is
still missing $4$. So the vertex $X_{v}(5)$ contains the vertex $u^{\prime}$
and we have $X_{v}(5)=X_{v}(3)$.

Since the cycle ${\mathcal{V}}$ is minimum, by Observation 21, it is tight. In
the coloring $\beta^{\prime\prime}$, the vertex $x$ is now missing the color
$5$, we now apply a sequence a of Kempe swaps of the form
$K_{x}(m(v_{t-1}),m(v_{t}))$ for $t\in(j^{\prime}-1,j^{\prime}-2,\cdots,j+1)$
to obtain a coloring $\beta_{3}$ where $m(x)=m(v_{j-1})=2$. Note that each of
these swaps is ${\mathcal{V}}$-stable since after each swap the fan
${\mathcal{V}}$ is a minimum cycle and thus is tight. Moreover, since no edge
of ${\mathcal{U}}$ between $uy_{2}$ and $uu^{\prime}$ is colored with a color
in $\beta^{\prime}({\mathcal{V}})$, the coloring $\beta_{3}$ is
${\mathcal{U}}_{[y_{2},w]}$-equivalent to $\beta^{\prime\prime}$.

Hence we have $X_{u}(\beta_{3}(uy_{1}))_{\leqslant
w}=(uy_{1},uy_{2},\cdots,uw)$. The edge $uy_{1}$ may have been recolored
during the sequence of swaps, but in the coloring $\beta_{3}$, $uy_{1}$ is
guaranteed to be colored with a color in $\beta_{3}({\mathcal{V}})$. In the
coloring $\beta_{3}$, the vertices $x$ and $u$ are missing the same color $2$
and the vertex $v$ is still missing the color $1$. the cycle ${\mathcal{V}}$
is minimum, so it is saturated by Lemma 15, and therefore $x\not\in
K_{v}(1,2)$.

We swap the component $C_{1,2}=K_{x}(1,2)$ to obtain a coloring where $v$ and
$x$ are missing the same color $1$ and where the edge $vx$ is colored $4$. We
now swap the edge $vx$, and denote by $\beta_{4}$ the coloring obtained after
theses swaps. The coloring $\beta_{4}$ is ${\mathcal{V}}$-equivalent to
$\beta_{3}$, and is also $X_{u}(\beta_{4}(uy_{1}))_{[y_{2},w]}$-equivalent to
the coloring $\beta_{3}$. The vertices $v$ and $w$ are missing the same color
$4$, so $X_{u}(\beta_{4}(uy_{1}))$ and ${\mathcal{V}}$ are not entangled in
this coloring, and thus by Lemma 24 we have a contradiction. ∎

######  Proposition 45.

In the coloring $\beta_{2}$, the vertex $x$ belongs to $K_{x}(2,4)$.

###### Proof.

Otherwise, assume that it is not the case. In the coloring $\beta_{2}$, the
fan ${\mathcal{V}}$ is a minimum cycle, so it is saturated by Lemma 15.
Therefore the vertex $u$ belongs to $K_{v}(2,4)$ and the vertex $w$ does not
belong to this component. By Proposition 43 $X_{u}(1)$ contains the vertex
$w$. We swap the component $C_{2,4}=K_{w}(2,4)$, and obtain a coloring
$\beta^{\prime\prime}$ ${\mathcal{V}}$-equivalent to $\beta^{\prime}$. By
Observation 20, the cycle ${\mathcal{V}}$ is still the same minimum cycle in
the coloring $\beta^{\prime\prime}$, and now the vertex $w$ is missing the
color $2$. The coloring $\beta^{\prime\prime}$ is also
$X_{u}(1)_{<w}$-equivalent to the coloring $\beta^{\prime}$, so where
$X_{u}(1)$ still contains the vertex $w$. The vertex $x$ is still missing the
color $4$, so we swap the edge $vu$ to obtain a coloring $\beta_{3}$ where
$X_{u}(1)$ contains the vertex $w$ missing the color $2$, and thus $X_{u}(1)$
is a path. By Lemma 24 we have a contradiction. ∎

We are now ready to prove the lemma. We need to distinguish whether or not
$j=j^{\prime}+1$.

######  Case 45.1 ($j=j^{\prime}+1$).

In this case, we have $\beta^{\prime}(vu)=m^{\beta^{\prime}}(u^{\prime})=3$.
In the coloring $\beta^{\prime}$, the fan ${\mathcal{V}}$ is saturated, so
$u^{\prime}\in K_{v}(1,3)$ and thus $uy_{1}\in K_{u^{\prime}}(1,3)$. Let
$C_{1,3}=K_{u^{\prime}}(1,3)\setminus\\{uy_{1},vu\\}$, $C_{1,3}$ is a
$(1,3)$-bichromatic path between $u^{\prime}$ and $y_{1}$. In the coloring
$\beta_{2}$, we consider the component $C_{2,4}=K_{w}(2,4)$; this component
contains the vertex $x$ by Proposition 45. After swapping $C_{2,4}$ we obtain
a coloring $\beta_{3}$ ${\mathcal{V}}$-equivalent to ${\mathcal{V}}$ where the
fan $X_{u}(1)$ is a path. By Observation 20 the fan ${\mathcal{V}}$ is still
the same minimum cycle in the coloring $\beta_{3}$. Moreover, the coloring
$\beta_{3}$ is $C_{1,3}$-equivalent to the coloring $\beta_{2}$, and thus
$C_{1,3}$-equivalent to the coloring $\beta^{\prime}$, so $C_{1,3}$ is still a
$(1,3)$-bichromatic path between $u^{\prime}$ and $y_{1}$.

By Proposition 43 there is no edge in $E(X_{u}(1))$ colored with a color in
$\beta_{4}({\mathcal{V}})$, so we invert $X_{u}(1)$ to obtain a coloring
$\beta_{5}$ that is $(C_{1,3}\cup({\mathcal{V}}\setminus\\{u\\}))$-equivalent
to $\beta_{4}$. In the coloring $\beta_{4}$, the vertex $y_{1}$ is missing the
color $1$, so $K_{u^{\prime}}(1,3)=C_{1,3}$, and we swap this component; we
denote by $\beta_{5}$ the coloring obtained after the swap.

In the coloring $\beta_{5}$, the vertices $u$ and $u^{\prime}$ a both missing
the color $1$, so we swap the edge $uu^{\prime}$ to obtain a coloring where
$u$ and $u^{\prime}$ are missing the color $4$. In the coloring $\beta_{5}$,
the fan $X_{v}(2)$ is now a path that we invert to obtain a coloring
$\beta_{6}$. In the coloring $\beta_{6}$, the edge $uw$ is colored $2$, and
the vertex $u$ is now missing the color $4$, so
$K_{u}(2,4)=C_{2,4}\cup\\{uw\\}$, and we swap back this component, we denote
by $\beta_{7}$ the coloring obtained after this swap. Note that since
$|\\{1,2,3,4\\}|=4$, we can swap back $C_{2,4}$ before $C_{1,3}$.

In the coloring $\beta_{7}$, the vertices $u$ and $v$ are both missing the
color $2$, and the edge $vu$ is colored $3$, so we swap the edge $vu$ to
obtain a coloring where $u$ and $v$ are both missing the color $4$. In the
coloring obtained after the swap, the vertices $u$ and $y_{1}$ are both
missing the color $3$, so the fan $X_{u}(4)$ is now a path that we invert. We
denote by $\beta_{8}$ the coloring obtained after the swap.

In the coloring $\beta_{8}$, the edge $uu^{\prime}$ is colored $1$, and the
edge $uy_{1}$ is colored $3$, so
$K_{u}(1,3)=C_{1,3}\cup\\{uu^{\prime},uy_{1}\\}$ and this component is a
$(1,3)$-bichromatic cycle that we swap. In the coloring obtained after the
swap, the component $K_{v}(3,4)=\\{uu^{\prime},u^{\prime}\\}$, and it suffices
to swap this component to obtain exactly ${\mathcal{V}}^{-1}(\beta^{\prime})$.
Since ${\mathcal{V}}$ is a minimum cycle, this is a contradiction.

So $j\neq j+1$, and since the role of $u$ and $u^{\prime}$ is symmetric, we
also have that $j^{\prime}\neq j+1$. Therefore, inn the cycle ${\mathcal{V}}$,
there exists a vertex $v_{j+1}$ and $v_{j-1}$ such that
$|\\{u,u^{\prime},v_{j-1},v_{j^{\prime}-1}\\}|=4$. Without loss of generality,
we assume that
$\beta^{\prime}(vu^{\prime})=m^{\beta^{\prime}}(v_{j^{\prime}-1})=5$, and that
$\beta^{\prime}(vu)=m^{\beta^{\prime}}(v_{j-1})=6$.

######  Case 45.2 ($j\neq j^{\prime}+1$).

For this case, we need to distinguish the cases based on the shape
of$C_{1,5}=K_{uy_{1}}(1,5)$. Since ${\mathcal{V}}$ is saturated in the
coloring $\beta^{\prime}$, by Proposition 44, $C_{1,5}$ also contains $v$ and
$v_{j^{\prime}-1}$, and therefore this component is a $(1,5)$-path in this
coloring. Moreover, the fan ${\mathcal{V}}$ is tight by Observation 21, so
$K_{v_{j-1}}(2,6)$ contains $vv_{j+1}$, and $vu$. Let
$C_{2,6}=K_{v_{j-1}}(2,6)\setminus\\{vu,vv_{j+1}\\}$. The path $C_{2,6}$ is a
$(2,6)$-bichromatic path between $v_{j+1}$ and $v_{j-1}$.

There are two cases, in the coloring $\beta^{\prime}$, either $C_{1,5}$ is
such that $u$ is between $v_{j^{\prime}-1}$ and $y_{1}$, or $y_{1}$ is between
$v_{j^{\prime}-1}$ and $u$. We start both cases by swapping
$C_{2,4}=K_{w}(2,4)$ in the coloring $\beta_{2}$, by Proposition 45 the vertex
$w$ belongs to this component, and after the swap we have $m(w)=m(x)=m(u)=2$.
By Proposition 43 $X_{u}(1)$ is a path that we invert to obtain a coloring
$\beta_{3}$
$(\\{uu^{\prime}\\}\cup({\mathcal{V}}\setminus\\{u\\}))$-equivalent to
$\beta_{2}$.

In the coloring $\beta_{3}$, depending on the shape of $C_{1,5}$, either $u$
is in $C=K_{v_{j^{\prime}-1}}(1,5)$, or $y_{1}$ belongs to this component. We
now have to distinguish the cases. Both cases are pretty similar, their proofs
rely on the same principle: apply Kempe swaps to reach a coloring where the
edges of $E({\mathcal{V}})\cup\\{vw^{\prime}\\}$ induce two fans that are
cycles smaller than ${\mathcal{V}}$ (and that are invertible since
${\mathcal{V}}$ is minimum).

######  Subcase 45.2.1 ($u$ belongs to $C$).

In this case, $C=K_{v_{j^{\prime}-1}}(1,5)$ is a $(1,5)$-bichromatic path
between $v_{j^{\prime}-1}$ and $u$ and there is a $(1,5)$-bichromatic path
$C^{\prime}$ between $y_{1}$ and $u^{\prime}$.

From the coloring $\beta_{3}$, we swap the component $C$ to obtain a coloring
$\beta_{4}$ where the fan
$X_{v}(5)=(vu^{\prime},vv_{j^{\prime}+1},\cdots,vv_{j-1},vu)$ is a cycle
strictly smaller that ${\mathcal{V}}$, so since ${\mathcal{V}}$ is minimum,
this cycle is invertible. Moreover, the fan
$X_{v}(1)=(vx,vv_{j+1},\cdots,vv_{j^{\prime}-1})$ is also a cycle strictly
smaller than ${\mathcal{V}}$, and so it is also invertible.

After inverting these two cycles, we obtain a coloring where the component
$K_{v_{j^{\prime}-1}}(1,5)=C\cup\\{vv_{j^{\prime}-1},vu\\}$ is
$(1,5)$-bichromatic cycle that we swap back; we denote by $\beta_{5}$ the
coloring obtained after the swap. Now the component $K_{y_{1}}(1,5)$ is
exactly $C^{\prime}$ and we swap it to obtain a coloring $\beta_{6}$.

In the coloring $\beta_{6}$, the fan
$X_{v}(3)=(vu^{\prime},vu,vv_{j-1}\cdots,vv_{j^{\prime}+1})$ is now a cycle
strictly smaller than ${\mathcal{V}}$, so we invert it. In the coloring
obtained after this inversion, the $(2,6)$-bichromatic path $C_{2,6}$ is still
a path between $v_{j+1}$ and $v_{j-1}$, but now $v_{j-1}$ is missing the color
$6$, and $v_{j+1}$ is missing the color $2$. So $K_{v_{j+1}}(2,6)=C_{2,6}$,
and we swap this component. Let $\beta_{7}$ be the coloring obtained after the
swap.

In the coloring $\beta_{7}$, the fan
$X_{v}(1)=(vu^{\prime},vv_{j^{\prime}+1},\cdots,vv_{j-1},vx)$ is now a cycle
strictly smaller than ${\mathcal{V}}$ and we invert it. In the coloring
obtained after the inversion, $K_{y_{1}}(1,5)$ is now exactly $C^{\prime}$,
and we swap back this component adn denote by $\beta_{8}$ the coloring
obtained after the swap.

In the coloring $\beta_{8}$, the vertices $y_{1}$ and $u$ are both missing the
color $1$, so the fan $X_{u}(2)$ is now a path that we invert to obtain a
coloring where $u$ and $w$ are missing the color $2$. In the coloring obtained
after the inversion, the component $K_{v_{j+1}}(2,6)$ is exactly
$C_{2,6}\cup\\{vv_{j-1},vu\\}$ and we swap back this component. In the
coloring obtained after the swap, the component $K_{w}(2,4)$ is exactly
$C_{2,4}$, and thus after swapping back this component, we obtain exactly
${\mathcal{V}}^{-1}(\beta^{\prime})$; a contradiction.

######  Subcase 45.2.2 ($y_{1}$ belongs to $C$).

In this case, $C=K_{v_{j^{\prime}-1}}(1,5)$ is a $(1,5)$-bichromatic path
between $v_{j^{\prime}-1}$ and $y_{1}$ and there is a $(1,5)$-bichromatic path
$C^{\prime}$ between $u$ and $u^{\prime}$. From the coloring $\beta_{3}$, we
swap the component $C$ to obtain a coloring where
$X_{v}(2)=(vv_{j+1},\cdots,vv_{j^{\prime}-1},vx)$ is a cycle strictly smaller
than ${\mathcal{V}}$, so it is invertible. After inverting it, we obtain a
coloring where the component $K_{v_{j-1}}(2,6)$ is exactly $C_{2,6}$. We swap
this component and denote by $\beta_{4}$ the coloring obtained after the swap.

In the coloring $\beta_{4}$, the fan
$X_{v}(1)=(vv_{j^{\prime}-1},\cdots,vv_{j+1},vu)$ is now a cycle stricly
smaller than ${\mathcal{V}}$, so it is invertible. After inverting it, the
component $K_{u^{\prime}}(1,5)$ is now exactly
$C^{\prime}\cup\\{vu^{\prime},vu\\}$ and so it is a $(1,5)$-bichromatic cycle
containing $vu$ and $vu^{\prime}$. After swapping this component, we obtain a
coloring where the fan
$X_{v}(1)=(vu^{\prime},vv_{j^{\prime}+1},\cdots,vv_{j-1},vx)$ is now a cycle
strictly smaller than ${\mathcal{V}}$, and we invert it. We denote by
$\beta_{5}$ the coloring obtained after the inversion.

In the coloring $\beta_{5}$, the component $K_{v_{j^{\prime}-1}}(1,5)$ is
exactly $C$, and we swap back this component. After the swap we obtain a
coloring where the fan $X_{v}(5)=(vu,vv_{j+1},\cdots,vv_{j^{\prime}-1})$ is
now a cycle strictly smaller than ${\mathcal{V}}$, and so we invert it and
denote by $\beta_{6}$ the coloring obtained after the swap.

In the coloring $\beta_{6}$, the component $K_{u^{\prime}}(1,5)$ is now
exactly $C^{\prime}$ and we swap back this component. After the swap we obatin
a coloring where $u$ and $y_{1}$ are both missing the color $1$, so the fan
$X_{u}(2)$ is now a path that we invert. We denote by $\beta_{7}$ the coloring
obtained after the swap.

In the coloring $\beta_{7}$ the component $K_{v_{j-1}}(2,6)$ is exactly
$C_{2,6}\cup\\{vv_{j-1},vu\\}$ and we swap it back. After the swap of this
component, we obtain a coloring where $K_{w}(2,4)$ is exactly $C_{2,4}$. After
swapping back this component, we obtain exactly
${\mathcal{V}}^{-1}(\beta^{\prime})$. This is a contradiction.

∎

From the previous lemma we derive the following corollary.

######  Corollary 46.

Let ${\mathcal{V}}=(vv_{1},\cdots,vv_{k})$ be a minimum cycle in a coloring
$\beta$, $u=v_{j}$ and $u^{\prime}=v_{j^{\prime}}$ two vertices of
${\mathcal{V}}$. If $uu^{\prime}\in E(G)$ and $\beta(uu^{\prime})=m(v)$, then
no fan around $v$ is a path.

###### Proof.

Assume that there exists a fan ${\mathcal{X}}$ around $v$ which is a path. It
suffices to swap the last edge $vx$ of ${\mathcal{X}}$ to obtain a coloring
$\beta_{2}$ $({\mathcal{V}}\cup\\{uu^{\prime}\\})$-equivalent to $\beta$ such
that $X_{v}(\beta_{2}(uu^{\prime}))=\\{vx\\}$ is now a path (of length one).
By Observation 20, the fan ${\mathcal{V}}$ is a minimum cycle in the coloring
$\beta_{2}$, so by Lemma 42, we get a contradiction. ∎

We are now ready to prove Lemma 41

###### Proof of Lemma 41.

Let ${\mathcal{V}}=(vv_{1},\cdots,vv_{k})$ be a minimum cycle in a coloring
$\beta$, $u=v_{j}$ and $u^{\prime}=v_{j^{\prime}}$ two vertices of
${\mathcal{V}}$. Without loss of generality, we assume that the vertices $v$,
$u$ and $u^{\prime}$ are respectively missing the colors $1$, $2$ and $3$. By
Lemma 24, the fan ${\mathcal{U}}=X_{u}(m(u^{\prime}))$ is a cycle entangled
with ${\mathcal{V}}$, so the edge $uu^{\prime}$ is in $E(G)$. Assume the
$\beta(uu^{\prime})\neq 1$.

We first prove that $X_{v}(\beta(uu^{\prime}))$ is a saturated cycle. If
$\beta(uu^{\prime})\in\beta({\mathcal{V}})$, then $X_{v}(\beta(uu^{\prime}))$
is exactly the fan ${\mathcal{V}}$. Since ${\mathcal{V}}$ is minimum, by Lemma
15, it is saturated, so $X_{v}(\beta(uu^{\prime}))$ is a saturated cycle as
desired.

Hence assume that $\beta(uu^{\prime})\not\in\beta({\mathcal{V}})$, and without
loss of generality, say $\beta(uu^{\prime})=4$. By Lemma 42, then fan
$X_{v}(4)$ is not a path.

We now prove that $X_{v}(4)$ is not a comet. Suppose that
$X_{v}(4)=(vw_{1},\cdots,vw_{t})$ is a comet. So there exists $i<t$ with
$m(w_{i})=m(w_{t})$, we denote by $c$ this color. If
$c\in\beta({\mathcal{V}})$, the cycle ${\mathcal{V}}$ is a subfan of the fan
$X_{v}(4)$, and thus $w_{t}=M({\mathcal{V}},c)\in V({\mathcal{V}})$ and
$w_{i}\not\in V({\mathcal{V}})$. Since ${\mathcal{V}}$ is minimum, it is
saturated by Lemma 15, so $w_{t}\in K_{v}(1,c)$, and thus $w_{i}\not\in
K_{v}(1,c)$. We now swap the component $K_{w_{i}}(1,c)$ and obtain a coloring
$\beta_{2}$ $({\mathcal{V}}\cup\\{uu^{\prime}\\})$-equivalent to $\beta$, so
the cycle ${\mathcal{V}}$ is also a minimum cycle in the coloring $\beta_{2}$
by Observation 20. In the coloring $\beta_{2}$, the fan
$X_{v}(\beta_{2}(uu^{\prime}))=X_{v}(4)$ is a now path, by Lemma 42 this is a
contradiction.

So $c\not\in\beta({\mathcal{V}})$. The vertices $w_{i}$ and $w_{t}$ are not
both part of $K_{v}(1,c)$. If $w_{i}$ is not in $K_{v}(1,c)$, we swap
$K_{w_{i}}(1,c)$ and obtain a coloring $\beta_{2}$,
$({\mathcal{V}}\cup\\{uu^{\prime}\\})$-equivalent to $\beta$. So the coloring
$\beta_{2}$, by Observation 20, the fan ${\mathcal{V}}$ is a minimum cycle.
But the fan $X_{v}(4)=X_{v}(\beta_{2}(uu^{\prime}))$ is now a path, a
contradiction by Lemma 42.

So the vertex $w_{i}$ belongs to the component $K_{v}(1,c)$ and thus $w_{t}$
does not belong to this component. We now swap $K_{w_{t}}(1,c)$ and obtain a
coloring $\beta_{2}$ which is
$({\mathcal{V}}\cup\\{uu^{\prime}\\})$-equivalent to $\beta$. So by
Observation 20, the fan ${\mathcal{V}}$ is still the same minimum cycle in
$\beta_{2}$, but the fan $X_{v}(4)=X_{v}(\beta_{2}(uu^{\prime}))$ is now a
path, again a contradiction by Lemma 42.

Therefore the fan $X_{v}(4)$ is a cycle. We now prove that is it saturated.
Note that since $X_{v}(4)$ is a cycle,
$\beta(X_{v}(4))\cap\beta({\mathcal{V}})=\\{1\\}$. Assume that
$X_{v}(4)=(vw_{1},\cdots,vw_{t})$ is not saturated, so there exists $i$ such
that $w_{i}\not\in K_{v}(1,m(w_{i}))$. We now have to distinguish whether
$w_{i}=w_{t}$ or not.

######  Case 46.1 ($w_{i}\neq w_{t}$).

This case is similar to the case where $X_{v}(4)$ is a comet. In this case,
the vertex $w_{i}$ is missing a color which is not in $\\{1,2,3,4\\}$, and we
can assume without loss of generality that $m(w_{i})=5$. Since $w_{i}$ does
not belong to $K_{v}(1,5)$, we swap the component $K_{w_{i}}(1,5)$ to obtain a
coloring $\beta_{2}$ $({\mathcal{V}}\cup\\{uu^{\prime}\\})$-equivalent to
$\beta$. In the coloring $\beta_{2}$, by Observation 20, the fan
${\mathcal{V}}$ is the same minimum cycle, but the fan
$X_{v}(4)=(w_{1},\cdots,w_{i})$ is now a path, a contradiction by Lemma 42.

######  Case 46.2 ($w_{i}=w_{t}$).

In this case, $w_{t}$ does not belong to $K_{v}(1,4)$. We first swap the
component $C_{1,4}=K_{w_{t}}(1,4)$. If $uu^{\prime}\not\in C_{1,4}$, then we
obtain a coloring $\beta_{2}$ $({\mathcal{V}}\cup\\{uu^{\prime}\\})$
equivalent to $\beta$. So by Observation 20, the fan ${\mathcal{V}}$ is a
minimum cycle in the coloring $\beta_{2}$, but now the fan
$X_{v}(4)=X_{v}(\beta_{2}(uu^{\prime}))=(vw_{1},\cdots,vw_{t})$ is now a path;
a contradiction by Lemma 42.

So the edge $uu^{\prime}$ is in $C_{1,4}$. After swapping $C_{1,4}$, we obtain
a coloring $\beta_{2}$ $({\mathcal{V}})$-equivalent to $\beta$, so
${\mathcal{V}}$ is still a minimum cycle. But now $\beta_{2}(uu^{\prime})=1$,
and $X_{v}(4)$ is a path, so by Corollary 46, we have a contradiction.

Hence $X_{v}(4)$ is a saturated cycle as desired.

∎

The proof of $P(0)$ is a direct consequence of the two previous lemmas.

###### Proof of Lemma 40.

Let ${\mathcal{V}}$ be a minimum cycle around a vertex $v$ in a coloring
$\beta$, $u$ and $u^{\prime}$ two vertices of ${\mathcal{V}}$,
${\mathcal{U}}=X_{u}(m(u^{\prime}))=(uu_{1},\cdots,uu_{l})$, assume that
$\beta(uu^{\prime})\neq m(v)$ and let
${\mathcal{W}}=X_{v}(\beta(uu_{l}))=(vw_{1},\cdots,vw_{s})$. Without loss of
generality, we assume that the vertices $v$, $u$ and $u^{\prime}$ are
respectively missing the colors $1$, $2$, and $3$, and that the edge
$uu^{\prime}$ is colored $4$.

We first prove that ${\mathcal{W}}$ is a saturated cycle containing $u_{l-1}$.
By Lemma 41, the fan ${\mathcal{W}}$ is a saturated cycle, and thus $w_{s}$ is
missing the color $4$. We now prove that the fan ${\mathcal{W}}$ contains the
vertex $u_{l-1}$.

If $4\in\beta({\mathcal{V}})$, then ${\mathcal{W}}={\mathcal{V}}$, and since
${\mathcal{U}}$ is entanlged with ${\mathcal{V}}$ by Lemma 24, we have that
$u_{l-1}=w_{s}\in{\mathcal{V}}={\mathcal{W}}$. So the color $4$ is not in
$\beta({\mathcal{V}})$.

Assume that the fan ${\mathcal{W}}$ does not contain $u_{l-1}$, so in
particular, $u_{l-1}\neq w_{s}$. The cycle ${\mathcal{W}}$ is saturated, so
$w_{s}\in K_{v}(1,4)$, and thus $u_{l-1}\not\in K_{v}(1,4)$. By Lemma 49

  * •

$u\in K_{u_{l-1}}(1,4)$,

  * •

there exists $j\leqslant l-1$ such that $\beta(uu_{j})=1$, and

  * •

the subfan $(uu_{j+1},\cdots,uu_{l-1})$ is a $({\mathcal{V}},u)$-independent
subfan.

We now consider the coloring $\beta^{\prime}$ obtained from $\beta$ after
swapping the component $C_{1,4}=K_{u_{l-1}}(1,4)$. Let
${\mathcal{X}}=(uu_{j+1},\cdots,uu_{l-1})$. The coloring $\beta^{\prime}$ is
$({\mathcal{V}}\cup{\mathcal{W}}\cup({\mathcal{X}}\setminus\\{u_{l-1}\\}))$-equivalent
to $\beta$, so ${\mathcal{V}}$ is a minimum by Observation 20, and
${\mathcal{W}}=X_{v}(4)$ is still a cycle. The vertex $v$ is still missing the
color $1$, but now the vertex $u_{l-1}$ is missing the color $1$, the edge
$uu_{j}$ is colored $4$, and the edge $uu_{l}$ is colored $1$. So now
$X_{u}(4)={\mathcal{X}}^{\prime}=(uu_{j},\cdots,uu_{i})$ is a
$({\mathcal{V}},u)$-independent subfan avoiding the vertex $v$. By Lemma 34
the fan $X_{v}(4)$ is a path; a contradiction. ∎

We now prove some properties of the fans around a vertex of a minimum cycle.

###  4.3 Fans around the vertices of a minimum cycle

We first prove that some fans around a vertex of a minimum cycle are not
paths.

######  Proposition 47.

Let ${\mathcal{V}}=(v_{1},\cdots,v_{k})$ be a minimum cycle in a coloring
$\beta$, $u=v_{j}$ and $u^{\prime}=v_{j^{\prime}}$ two vertices of
${\mathcal{V}}$, and
${\mathcal{U}}=X_{u}(m(u^{\prime}))=(uu_{1},\cdots,uu_{l})$, and $w=u_{s}$ a
vertex of ${\mathcal{U}}$. Then for any color $c\in\beta({\mathcal{V}})$, the
fan ${\mathcal{W}}=X_{w}(c)=(ww_{1},\cdots,ww_{t})$ is not a path.

###### Proof.

Otherwise assume that the fan ${\mathcal{W}}$ is a path. The vertex $w$ is not
a vertex of $V({\mathcal{V}})$, otherwise since ${\mathcal{W}}$ is a path, by
Lemma 24 we have a contradiction. So the vertex $w$ is not in
$V({\mathcal{V}})$.

We invert it until we reach a coloring $\beta_{2}$ where
$m^{\beta_{2}}(w)\in\beta({\mathcal{V}}\cup{\mathcal{U}}_{<s})$, we denote by
$c^{\prime}$ this new missing color. Since $c\in\beta({\mathcal{W}})$, the
color $c^{\prime}$ is well defined. The coloring $\beta_{2}$ is
$({\mathcal{V}}\cup{\mathcal{U}}_{<s})$-equivalent to $\beta$. Thus by
Observation 20, the sequence ${\mathcal{V}}$ is still a minimum cycle in the
coloring $\beta_{2}$. Let
${\mathcal{U}}^{\prime}=X_{u}(m^{\beta_{2}}(u^{\prime}))=(uu^{\prime}_{1},\cdots,uu^{\prime}_{l^{\prime}})$.
Since $\beta_{2}$ is $({\mathcal{U}}_{<s})$-equivalent to $\beta$, we have
that ${\mathcal{U}}_{<s}={\mathcal{U}}^{\prime}_{<s}$, so the edge $uw$ is
also in $E({\mathcal{U}}^{\prime})$, it is exactly the edge $uu^{\prime}_{s}$.
If $c^{\prime}\in\beta({\mathcal{V}})$, then ${\mathcal{U}}^{\prime}$ is not
entangled with ${\mathcal{V}}$ in the coloring $\beta_{2}$, a contradiction by
Lemma 24. If $c^{\prime}\in\beta{{\mathcal{U}}_{<s}}$, then
${\mathcal{U}}^{\prime}$ is now a comet in the coloring $\beta_{2}$, again, by
Lemma 24 we have a contradiction. ∎

######  Lemma 48.

Let $i\geqslant 0$, ${\mathcal{V}}$ be a minimum cycle in a coloring $\beta$,
$u$ and $u^{\prime}$ two vertices of ${\mathcal{V}}$,
${\mathcal{U}}=X_{u}(m(u^{\prime}))=(uu_{1},\cdots,uu_{l})$, and
$c\in\beta({\mathcal{V}})\cup\beta({\mathcal{U}}_{<u_{i}})$. If $u_{i}\not\in
V({\mathcal{V}})\cup\\{v\\}$. Then the fan
${\mathcal{X}}=X_{u_{i}}(c)=(u_{i}x_{1},\cdots,u_{i}x_{s})$ is not a path.

###### Proof.

Assume $u_{i}\not\in V({\mathcal{V}})$ and that ${\mathcal{X}}$ is a path.
Without loss of generality, we assume that there is no edge in
${\mathcal{X}}_{[x_{2},x_{s}]}$ colored with a color in
$\beta({\mathcal{V}})\cup\beta({\mathcal{U}}_{<u_{i}})$, otherwise, it
suffices to consider the subfan of ${\mathcal{X}}$ starting with this edge,
this fan is also a path. We now invert ${\mathcal{X}}$ and obtain a coloring
$\beta^{\prime}$ where $m(u_{i})=c$. The coloring $\beta^{\prime}$ is
$({\mathcal{V}}\cup{\mathcal{U}}_{<u_{i}})$-equivalent to $\beta$. So by
Observation 20, the fan ${\mathcal{V}}$ is a minimum cycle in the coloring
$\beta^{\prime}$. If $c\in\beta({\mathcal{V}})$, now the fan
$X_{u}(m(u^{\prime}))$ contains the vertex $u_{i}$ which is missing the color
$c\in\beta({\mathcal{V}})$, so $X_{u}(m(u^{\prime}))$ is not entangled with
${\mathcal{V}}$. If $m(u_{i})\in\beta({\mathcal{U}}_{<u_{i}}$, let
$u^{\prime\prime}=M({\mathcal{U}}_{<u_{i}},c)$. Then $X_{u}(m(u^{\prime}))$ is
now a comet since it contains the vertices $u_{i}$ and $u^{\prime\prime}$ both
missing the color $c$. In both cases, by Lemma 24 we have a contradiction. ∎

We now prove a sufficient condition for a fan around a vertex of a minimum to
contain an edge colored with the color missing at the central vertex of the
minimum cycle.

######  Lemma 49.

Let ${\mathcal{V}}$ be a minimum cycle in a coloring $\beta$, $u$ and
$u^{\prime}$ two vertices of ${\mathcal{V}}$,
${\mathcal{U}}=X_{u}(m(u^{\prime}))=(uu_{1},\cdots,uu_{l})$ and $i\leqslant
l$. If $\beta(uu_{i})\neq m(v)$, $m(u_{i})\not\in\beta({\mathcal{V}})$ and
$u_{i}\not\in K_{v}(m(v),m(u_{i}))$, then:

  * •

$u\in K_{u_{i}}(m(v),m(u_{i}))$,

  * •

there exists $j<i$ such that $\beta(uu_{j})=m(v)$, and

  * •

the subfan $(uu_{j+1},\cdots,uu_{i})$ is a $({\mathcal{V}},u)$-independent
subfan.

###### Proof.

Let ${\mathcal{V}}$, $u$, $u^{\prime}$ and ${\mathcal{U}}$ be as in the lemma.
Without loss of generality, we assume that the vertices $v$, $u$, and
$u^{\prime}$ are respectively missing the colors $1$, $2$ and $3$. Assume that
$u_{i}\not\in K_{v}(1,m(u_{i}))$. Since the cycle ${\mathcal{V}}$ is minimum,
by Lemma 15 it is saturated, so for any $u^{\prime\prime}\in
V({\mathcal{V}})$, $u^{\prime\prime}\in K_{v}(m(v),m(u^{\prime\prime}))$, thus
$u_{i}\not\in V({\mathcal{V}})$, so without loss of generality, we may assume
that $u_{i}$ is missing the color $4$. We first consider the component
$C_{1,4}=K_{u_{i}}(1,4)$. In the coloring $\beta$, by Lemma 24,
${\mathcal{U}}$ is a cycle entangled with ${\mathcal{V}}$, so it does not
contain any other vertex missing $4$. Since $v\not\in C_{1,4}$, then
$V(C_{1,4})\cap V({\mathcal{U}})=\\{u_{i}\\}$. After swapping $C_{1,4}$, we
obtain a coloring $\beta^{\prime}$
$(V({\mathcal{U}})\setminus\\{u_{i}\\})$-identical to $\beta$ where $u_{i}$ is
now missing the color $1$. Note that the coloring $\beta^{\prime}$ is also
${\mathcal{V}}$-equivalent to $\beta$, and thus ${\mathcal{V}}$ is still a
minimum cycle in $\beta^{\prime}$. Moreover the vertex $v$ is still missing
the color $1$ in $\beta^{\prime}$.

We first prove that the vertex $u$ belongs to $C_{1,4}$ and that there is an
edge colored $1$ in $\\{uu_{1},\cdots,uu_{i-1}\\}$. If $u\not\in C_{1,4}$, or
if there is no edge colored $1$ in $\\{uu_{1},\cdots,uu_{i-1}\\}$, then the
coloring $\beta^{\prime}$ is also
$(E({\mathcal{U}}_{[uu_{1},uu_{i}]}))$-identical to $\beta$, and so $X_{u}(3)$
now contains the vertex $u_{i}$ which is missing the color $1$, so $X_{u}(3)$
is not a cycle entangled with ${\mathcal{V}}$. Since the cycle ${\mathcal{V}}$
is minimum, we have a contradiction by Lemma 24. So $u\in C_{1,4}$ and there
is an edge $uu_{j}$ with $j<i$ colored $1$.

We now prove that $(uu_{j+1},\cdots,uu_{i})$ is a
$({\mathcal{V}},u)$-idenpendent subfan. Note that we have have $j+1=i$ (i.e.
the subfan is of length $1$). Since $\beta^{\prime}$ is
$(V({\mathcal{U}})\setminus\\{u_{i}\\})$-identical to $\beta$, the sequence
$(uu_{j+1},\cdots,uu_{i})$ is a subfan. Assume that there exists
$s\in\\{j+1,\cdots,i\\}$ such that $\beta(uu_{s})\in\beta({\mathcal{V}})$.
Then, in the coloring $\beta^{\prime}$, $X_{u}(\beta(uu_{s}))$ contains the
vertex $u_{i}$ that is missing the color $1$, thus it is not a cycle entangled
with ${\mathcal{V}}$, by Lemma 24, this is a contradiction. ∎

######  Lemma 50.

Let ${\mathcal{V}}$ be a minimum cycle in a coloring $\beta$, $u$ and
$u^{\prime}$ two vertices of ${\mathcal{V}}$,
${\mathcal{U}}=X_{u}(m(u^{\prime}))=(uu_{1},\cdots,uu_{l})$ and $i\leqslant l$
such that $m(u_{i})\not\in\beta({\mathcal{V}})$. Let $\beta^{\prime}$ be a
coloring obtained from $\beta$ by swapping a $(m(v),c)$-component $C$ that
does not contain $v$ for some color
$c\not\in(\beta({\mathcal{U}}_{<u_{i}})\cup\\{m(v)\\})$. If there exists a
coloring $\beta^{\prime\prime}$ such that:

  * •

$\beta^{\prime\prime}$ is
$({\mathcal{V}}\cup{\mathcal{U}}_{<u_{i}})$-equivalent to $\beta^{\prime}$,
and

  * •

$m^{\beta^{\prime\prime}}(u_{i})\in\beta^{\prime\prime}({\mathcal{V}})\cup\beta^{\prime\prime}({\mathcal{U}}_{<u_{i}})$.

Then

  * •

$u\in C$,

  * •

there exists $j<i$ such that $\beta(uu_{j})=m(v)$, and

  * •

the subfan $(uu_{j+1},\cdots,uu_{i})$ is a $({\mathcal{V}},u)$-independent
subfan in $\beta$.

###### Proof.

Let ${\mathcal{V}}$, ${\mathcal{U}}$, $u$, $u^{\prime}$, $\beta^{\prime}$, and
$c$ be as in the lemma. Without loss of generality, we assume that the
vertices $v$, $u$, and $u^{\prime}$ are respectively missing the colors $1$,
$2$ and $3$. Assume that there exists such a coloring $\beta^{\prime\prime}$.
Note that since $m(u_{i})\not\in\beta({\mathcal{V}})$, the vertex $u_{i}$ is
not in ${\mathcal{V}}$. The cycle ${\mathcal{V}}$ is a minimum cycle in
$\beta$, so it is saturated by Lemma 15. Therefore, if
$c\in\beta({\mathcal{V}})$, then $M({\mathcal{V}},c)\in K_{v}(1,c)$, and thus
$M({\mathcal{V}},c)\not\in C$. So $\beta^{\prime}$ is
$V({\mathcal{V}})$-equivalent to $\beta$. Moreover, $v\not\in C$ so
$\beta^{\prime}$ is also $(E({\mathcal{V}})\cup\\{v\\})$-equivalent to
$\beta$. Therefore, the coloring $\beta^{\prime}$ is
$({\mathcal{V}}\cup\\{v\\})$-equivalent to $\beta$.

We first prove that the vertex $u$ belongs to $C$ and that there exists an
edge colored $1$ in ${\mathcal{U}}_{<u_{i}}$. Assume that $u$ does not belong
to $C$, or that there is no edge colored $1$ in ${\mathcal{U}}_{<u_{i}}$ in
$\beta$. We show that $\beta^{\prime\prime}$ is
$({\mathcal{V}}\cup{\mathcal{U}}_{<u_{i}})$-equivalent to $\beta$. To prove
it, it suffices to prove that $\beta^{\prime}$ is
${\mathcal{U}}_{<u_{i}}$-equivalent to $\beta$. The swap between $\beta$ and
$\beta^{\prime}$ only changes the colors of edges colored $1$ or $c$. Since
$\\{1,c\\}\cap\beta({\mathcal{U}}_{<u_{i}})=\emptyset$ this means that the
coloring $\beta^{\prime}$ is ${\mathcal{U}}_{<u_{i}}$-equivalent to $\beta$.
Since $\beta^{\prime}$ is also $({\mathcal{V}}\cup\\{v\\})$-equivalent to
$\beta$ , in total it is
$({\mathcal{V}}\cup{\mathcal{U}}_{<u_{i}})$-equivalent to $\beta$. Note that
the missing color of $v$ may be different in $\beta^{\prime}$ and
$\beta^{\prime\prime}$. Since $\beta^{\prime\prime}$ is
$({\mathcal{V}}\cup{\mathcal{U}}_{<u_{i}})$-equivalent to $\beta^{\prime}$,
the coloring $\beta^{\prime\prime}$ is
$({\mathcal{V}}\cup{\mathcal{U}}_{<u_{i}})$-equivalent to $\beta$. Note that
the missing color of $v$ may be different in $\beta^{\prime}$ and
$\beta^{\prime\prime}$. Hence, in the coloring $\beta^{\prime\prime}$, by
Observation 20, the cycle ${\mathcal{V}}$ is a minimum cycle and we have that
$X_{u}(m(u^{\prime}))$ now contains the vertex $u_{i}$ which is missing a
color in
$(\beta^{\prime\prime}({\mathcal{V}})\cup\beta^{\prime\prime}({\mathcal{U}}_{<u_{i}}))$.
Let $c^{\prime}$ be this color. Since the cycle ${\mathcal{V}}$ is minimum in
$\beta^{\prime\prime}$, by Lemma 24, $X_{u}(m(u^{\prime}))$ is a cycle
entangled with ${\mathcal{V}}$. If
$c^{\prime}\in\beta^{\prime\prime}({\mathcal{V}})$, then
$X_{u}(m(u^{\prime}))$ is not entangled with ${\mathcal{V}}$, and if
$c^{\prime}\in\beta^{\prime\prime}({\mathcal{U}}_{<u_{i}})$ then
$X_{u}(m(u^{\prime}))$ is a comet. In both cases, we have a contradiction. So
$u\in C$, and there exists $j<i$ such that $\beta(uu_{j})=1$.

We now prove that the subfan ${\mathcal{X}}=(uu_{j+1},\cdots,uu_{i})$ is a
$({\mathcal{V}},u)$-independent subfan in $\beta$. Note that we have have
$j+1=i$ (i.e. the subfan is of length $1$). If ${\mathcal{X}}$ is not a
$({\mathcal{V}},u)$-independent subfan, then there exists
$s\in\\{j+1,\cdots,i\\}$ such that
$c^{\prime}\in\beta(uu_{s})\in\beta({\mathcal{V}})$. Recall that the coloring
$\beta^{\prime}$ is $({\mathcal{V}}\cup\\{v\\})$-equivalent to $\beta$, and
thus that $\beta^{\prime\prime}$ is also
$({\mathcal{V}}\cup\\{v\\})$-equivalent to $\beta$. In the coloring
$\beta^{\prime}$, the edge $uu_{j}$ is now colored $c$, and this is the only
edge in $E({\mathcal{U}}_{<u_{i}})$ that has been recolored during the swap of
$C$. Moreover, the cycle ${\mathcal{V}}$ is minimum in $\beta$, and thus by
Lemma 24, then fan ${\mathcal{U}}$ is a cycle, and does not contain any vertex
missing the color $1$ in $V({\mathcal{U}}_{[}u_{j},u_{i}])$. Since
$c\not\in\beta({\mathcal{U}}_{<u_{i}})$, the coloring $\beta^{\prime}$ is also
$V({\mathcal{U}}_{[}u_{j},u_{i}])$-equivalent to the coloring $\beta$, and so
it is ${\mathcal{X}}$-equivalent to $\beta$. The coloring
$\beta^{\prime\prime}$ is ${\mathcal{U}}_{<u_{i}}$-equivalent to
$\beta^{\prime}$, so it is $({\mathcal{X}}\setminus\\{u_{i}\\}$-equivalent to
$\beta$ and thus the fan $X_{u}(c^{\prime})$ now starts with the edge $uu_{s}$
and contains the vertex $u_{i}\not\in V({\mathcal{V}})$ which is missing a
color in $\beta({\mathcal{V}})=\beta^{\prime\prime}({\mathcal{V}})$. Since
${\mathcal{V}}$ is also a minimum cycle in $\beta^{\prime\prime}$, by Lemma
24, $X_{v}(c^{\prime})$ is a cycle entangled with ${\mathcal{V}}$; this is a
contradiction. ∎

In the following section we prove some properties that are guaranteed if the
property $P$ is true up to some $i$.

###  4.4 Properties guaranteed by $P(i)$

The following lemma guarantees that the last vertices of two cycles will be
the same.

######  Lemma 51.

Let $i\geqslant 0$, ${\mathcal{V}}$ be a minimum cycle around a vertex $v$ in
a coloring $\beta$, $u$ and $u^{\prime\prime}$ two vertices of
${\mathcal{V}}$,
${\mathcal{U}}=X^{\beta}_{u}(m^{\beta}(u^{\prime\prime}))=(uu_{1},\cdots,uu_{l})$,
$\beta^{\prime}$ a coloring
$({\mathcal{V}}\cup{\mathcal{U}}_{[u_{l-(i-1))},u_{l}]}\cup\bigcup\limits_{j\in[0,i-1]}X_{v}(\beta(uu_{l-j}))$-equivalent
to $\beta$ and
${\mathcal{U}}^{\prime}=X^{\beta^{\prime}}_{u}(m^{\beta^{\prime}}(u^{\prime\prime}))=(uu^{\prime}_{1},\cdots,uu^{\prime}_{s})$.
If

  * •

for any $j<i$ $P(j)$ is true, and

  * •

$\\{m^{\beta}(v),m^{\beta^{\prime}}(v)\\}\cap\beta({\mathcal{U}}_{[u_{l-(i-1)},u_{l}]}))=\emptyset$

then for any $t\leqslant i$, $u_{l-t}=u^{\prime}_{s-t}$.

###### Proof.

Let $i$, ${\mathcal{V}}$, ${\mathcal{U}}$, ${\mathcal{U}}^{\prime}$, $\beta$,
$\beta^{\prime}$, $v$, $u$, and $u^{\prime\prime}$ be as in the lemma. Assume
that $P(j)$ is true for all $j<i$, that
$\\{m^{\beta}(v),m^{\beta^{\prime}}(v)\\}\cap\beta({\mathcal{U}}_{[u_{l-(i-1)},u_{l}]}))=\emptyset$
and that there exists $t\leqslant i$ such that $u_{l-t}\neq u_{s-t}$, without
loss of generality, we may assume that such a $t$ is minimum. The cycle
${\mathcal{V}}$ is a minimum cycle in $\beta$, and $\beta^{\prime}$ is
${\mathcal{V}}$-equivalent to $\beta$, so by Observation 20, the cycle
${\mathcal{V}}$ is also a minimum cycle in the coloring $\beta^{\prime}$.
Therefore by Lemma 24, the fans ${\mathcal{U}}$ and ${\mathcal{U}}^{\prime}$
are both cycles entangled with ${\mathcal{V}}$ respectively in $\beta$ and
$\beta^{\prime}$. Note that since
$m^{\beta}(v)\not\in\beta({\mathcal{U}}_{[u_{l-(i-1)},u_{l}]}))$, and that
$P(j)$ is true for all $j<i$, for all $j<i$, the fan $X_{v}(\beta(uu_{l-j})$
is a cycle containing $u_{l-j-1}$. Moreover, this also means that no vertex in
$V({\mathcal{U}}_{[u_{l-i},u_{l}]})$ is missing the color $m(v)$, and thus
none of them is $v$. Therefore the vertex $v$ may be missing a different color
in $\beta$ and in $\beta^{\prime}$. Note also that, in the coloring $\beta$,
the edge $uu_{l-i}$ may be colored $m^{\beta}(v)$ or $m^{\beta^{\prime}}(v)$.

We first show that $t\neq 0$. Since the fans ${\mathcal{U}}$ and
${\mathcal{U}}^{\prime}$ are both cycles we have
$m^{\beta}(u_{l})=m^{\beta^{\prime}}(u_{s})=m^{\beta}(u^{\prime\prime})$, and
moreover, ${\mathcal{U}}$ and ${\mathcal{U}}^{\prime}$ are entangled with
${\mathcal{V}}$ so $u_{l}=u^{\prime\prime}=u^{\prime}_{s}$, and thus $t\neq
0$.

Since $t$ is minimum, $u_{l-(t-1)}=u^{\prime}_{s-(t-1)}$. Moreover,
$\beta^{\prime}$ is ${\mathcal{U}}_{[u_{l-(i-1)},u_{l}]}$-equivalent to
$\beta$, so in particular
$\beta(uu_{l-(t-1)})=\beta^{\prime}(uu_{l-(t-1)})=\beta^{\prime}(uu^{\prime}_{s-(t-1)})$,
without loss of generality, we assume that this color is $1$. This means that
both the vertices $u_{l-t}$ and $u^{\prime}_{s-t}$ are missing the color $1$.
To reach a contradiction we show that both these vertices belong to a same
cycle. Since $1\neq m^{\beta}(v)$ and $P(t-1)$ is true, then $X^{\beta}(1)$ is
a cycle containing $u_{l-t}$. Similarly $1\neq m^{\beta^{\prime}}(v)$ and
$P(t-1)$ is true so $X^{\beta^{\prime}}_{v}(1)$ is a cycle containing
$u^{\prime}_{s-t}$. However, the coloring $\beta^{\prime}$ is
$(\bigcup\limits_{j\in[0,i-1]}X_{v}(\beta(uu_{l-j}))$-equivalent to the
coloring $\beta$, so in particular
$X^{\beta}_{v}(1)=X^{\beta^{\prime}}_{v}(1)$; we denote by ${\mathcal{X}}$
this fan. The fan ${\mathcal{X}}$ is a cycle and contains two vertices
$u_{l-t}$ and $u_{s-t}$ that are both missing the color $1$, this is a
contradiction.

∎

Now we prove that we can guarantee that there is no path around the central
vertex of a minimum cycle

######  Lemma 52.

Let $i\geqslant 0$, ${\mathcal{V}}$ be a minimum cycle around a vertex $v$ in
a coloring $\beta$, $u$ and $u^{\prime\prime}$ two vertices of
${\mathcal{V}}$,
${\mathcal{U}}=X^{\beta}_{u}(m(u^{\prime\prime}))=(uu_{1},\cdots,uu_{l})$, and
${\mathcal{X}}=(vx_{1},\cdots,vx_{s})$ a fan around $v$. If

  * •

for any $j<i$ $P(j)$ is true,

  * •

$P_{weak}(i)$ is true, and

  * •

$\beta(uu_{l-i})=m(v)$,

then ${\mathcal{X}}$ is not a path.

###### Proof.

Let $i$, ${\mathcal{V}}$, ${\mathcal{U}}$, ${\mathcal{X}}$, $\beta$, $v$, $u$,
and $u^{\prime\prime}$ be as in the lemma, and without loss of generality we
assume that $m(v)=1$. Assume that for any $j<i$ $P(j)$ is true, that
$P_{weak}(i)$ is true, that $\beta(uu_{l-i})=m(v)$ and that ${\mathcal{X}}$ is
a path. The fan ${\mathcal{X}}$ is a path so the vertex $x_{s}$ is also
missing the color $1$, without loss of generality, we assume that
$\beta(vx_{s})=2$. Note that this means that $X_{v}(2)$ is also a path (of
length $1$). The cycle ${\mathcal{V}}$ is minimum and by Lemma 24 the fan
${\mathcal{U}}$ is a cycle entangled with ${\mathcal{V}}$. Since
$\beta(uu_{l-i})=1$, no edge in $E({\mathcal{U}}_{[u_{l-(i-1)},u_{l}]})$ is
colored $1$. Since $P(j)$ is true for all $j<i$, $X_{v}(\beta(uu_{l-j})$ is a
cycle for all $j<i$; since $X_{v}(2)$ is a path, no edge in
$E({\mathcal{U}}_{[u_{l-(i-1)},u_{l}]})$ is colored $2$ either.

We now consider the coloring $\beta^{\prime}$ obtained from $\beta$ by
swapping the edge $vx_{s}$. Note that in the coloring $\beta^{\prime}$, the
vertex $v$ is now missing the color $2$, and the fan
$X^{\beta^{\prime}}_{v}(1)$ is now a path (of length $1$). The coloring
$\beta^{\prime}$ is clearly ${\mathcal{V}}$-equivalent to $\beta$ so by
Observation 20, the fan ${\mathcal{V}}$ is a minimum cycle in the coloring
$\beta^{\prime}$. Let
${\mathcal{U}}^{\prime}=X^{\beta^{\prime}}_{u}(m(u^{\prime\prime}))=(uu^{\prime}_{1},\cdots,uu^{\prime}_{s}))$.
No edge in $E({\mathcal{U}}_{[u_{l-(i-1)},u_{l}]})$ is colored $1$, so no
vertex in $V({\mathcal{U}}_{[u_{l-i},u_{l}]})$ is missing the color $1$, and
thus $\beta^{\prime}$ is also
${\mathcal{U}}_{[u_{l-(i-1))},u_{l}]}$-equivalent to $\beta$. Finally since no
edge in $E({\mathcal{U}}_{[u_{l-(i-1)},u_{l}]})$ is colored $1$ and $P(j)$ is
true for all $j<i$, the fans $X_{v}(\beta(uu_{l-j}))$ are cycles for all
$j<i$. Therefore the coloring $\beta^{\prime}$ is also
$(\bigcup\limits_{j\in[0,i-1]}X_{v}(\beta(uu_{l-j}))$-equivalent to $\beta$.
By Lemma 51, for any $t\leqslant i$ $u_{l-t}=u^{\prime}_{s-t}$, so in
particular $u_{l-i}=u^{\prime}_{s-i}$. In the coloring $\beta^{\prime}$ the
edge $uu_{s-i}$ is still colored $1$, and now the vertex $v$ is missing the
color $2$. Since $P_{weak}(i)$ is true the fan $X^{\beta^{\prime}}_{v}(1)$ is
not a path, this is a contradiction. ∎

The next lemma considers $({\mathcal{V}},u)$-independent cycles.

######  Lemma 53.

Let $i\geqslant 0$, ${\mathcal{V}}$ be a minimum cycle in a coloring $\beta$,
$u$ and $u^{\prime}$ two vertices of ${\mathcal{V}}$,
${\mathcal{U}}=X_{u}(m(u^{\prime})=(uu_{1},\cdots,uu_{l})$, $h\leqslant i$
such that $\beta(uu_{l-h})=m(v)$, $c^{\prime}$ a color not in
$\beta({\mathcal{V}})$ such that
${\mathcal{Y}}=X_{u}(c^{\prime})=(uy_{1},\cdots,uy_{r})$ is a
$({\mathcal{V}},u)$-independent cycle different from ${\mathcal{U}}$ and
${\mathcal{X}}=X_{v}(c^{\prime})=(vx_{1},\cdots,vx_{s})$ is a cycle different
from ${\mathcal{V}}$ with $y_{r}=x_{s}=z$, and $c^{\prime\prime}$ a color in
$\beta({\mathcal{V}})$. If $P(j)$ is true for all $j\leqslant i$, then
${\mathcal{Z}}=X_{z}(c^{\prime\prime})$ is not a path.

###### Proof.

Without loss of generality, we assume that the vertices $v$, $u$ and
$u^{\prime}$ are respectively missing the colors $1$, $2$, and $3$; we also
assume that $c^{\prime}=4$. Note that since ${\mathcal{U}}$ and
${\mathcal{Y}}$ are different cycles, we have
$\beta({\mathcal{U}})\cap\beta({\mathcal{Y}})=\\{m(u)\\}=\\{2$}, and since
${\mathcal{X}}$ and ${\mathcal{V}}$ are different cycles, we have that
$\beta({\mathcal{V}})\cap\beta({\mathcal{X}})=\\{m(v)\\}=1$. Assume that the
fan ${\mathcal{Z}}$ is a path. The fan ${\mathcal{V}}$ is a minimum cycle, so
by Lemma 24, the fan ${\mathcal{U}}$ is a cycle entangled with
${\mathcal{V}}$, and thus $u_{l}=u^{\prime}$.

We first invert ${\mathcal{Z}}$ until we reach a coloring $\beta^{\prime}$
where
$m(z)=c\in(\beta({\mathcal{V}})\cup\beta({\mathcal{X}})\cup\beta({\mathcal{Y}}))\setminus\\{4\\}$.
The coloring $\beta^{\prime}$ is ${\mathcal{V}}$-equivalent to $\beta$, so by
Observation 20, the cycle ${\mathcal{V}}$ is the same minimum cycle in the
coloring $\beta^{\prime}$. The coloring $\beta^{\prime}$ is also
${\mathcal{U}}$-equivalent to $\beta$, so, in the coloring $\beta^{\prime}$,
the fan $X_{u}(3)$ is exactly ${\mathcal{U}}$. Since the property $P(j)$ is
true for all $j\leqslant h$, for any $j\leqslant h$ such that
$\beta(uu_{l-j})\neq 1$, the fan $X_{v}(\beta(uu_{l-j}))$ is a saturated cycle
containing $u_{l-j-1}$.

We first show that $c\not\in\beta({\mathcal{V}})$. Otherwise, assume that
$c\in\beta({\mathcal{V}})$, then $c\not\in\beta({\mathcal{Y}})$ since
${\mathcal{Y}}$ is a $({\mathcal{V}},u)$-independent cycle, and
$c\not\beta({\mathcal{X}})$ since ${\mathcal{X}}$ is different from
${\mathcal{V}}$. So the coloring $\beta^{\prime}$ is
$({\mathcal{X}}\cup{\mathcal{Y}}\setminus\\{z\\})$-equivalent to $\beta$.
Hence, in the coloring $\beta^{\prime}$, the fans $X_{u}(4)$ and $X_{v}(4)$
still contain the vertex $z$. If $c=1$, then in the coloring $\beta^{\prime}$,
since the fan $X_{u}(4)$ still contains the vertex $z$, we have that
$X_{u}(4)_{\leqslant z}$ is a $({\mathcal{V}},u)$-independent subfan avoiding
$v$. However, the fan $X_{v}(4)$ is now a path containing $z$, by Lemma 34, we
have a contradiction. So $c\not 1$. Since the fan ${\mathcal{V}}$ is a minimum
cycle in the coloring $\beta^{\prime}$, it is saturated by Lemma 15, thus
$z\not\in K_{v}(1,c)$. We now swap the component $C_{1,c}=K_{z}(1,c)$, and
denote by $\beta^{\prime\prime}$ the coloring obtained after the swap. The
coloring $\beta^{\prime\prime}$ is ${\mathcal{V}}$-equivalent to
$\beta^{\prime}$, so ${\mathcal{V}}$ is still a minimum cycle in the coloring
$\beta^{\prime\prime}$ by Observation 20. The coloring $\beta^{\prime\prime}$
is also $(X_{u}(4)_{\leqslant z})\cup X_{v}(4))$-equivalent to
$\beta^{\prime}$, so the fan $X_{u}(4)$ still contains the vertex $z$ which is
now missing the color $1$. Similarly to the previous case, the subfan
$X_{u}(4)_{\leqslant z}$ is now a $({\mathcal{V}},u)$-independent subfan
avoiding $v$, and $X_{v}(4)$ is now a path; again by Lemma 34, we have a
contradiction. Without loss of generality, we assume that $c=5$.

######  Case 53.1 ($5\not\in\beta({\mathcal{X}})$).

In this case, the coloring $\beta^{\prime}$ is
$({\mathcal{X}}\setminus\\{z\\})$-equivalent to $\beta$, and so in the
coloring $\beta^{\prime}$, the fan $X_{v}(4)$ still contains the vertex $z$
which is now missing the color $5$.

######  Subcase 53.1.1 ($5\in\beta({\mathcal{U}}_{<u_{l-h}})$).

Let $z^{\prime}$ be the vertex of ${\mathcal{U}}_{<u_{l-h}}$ missing the color
$5$. If the vertex $z^{\prime}$ does not belong to $K_{v}(1,5)$, then we swap
the component $C_{1,5}=K_{z^{\prime}}(1,5)$, and denote by
$\beta^{\prime\prime}$ the coloring obtained after the swap. The coloring
$\beta^{\prime\prime}$ is clearly ${\mathcal{V}}$-equivalent to
$\beta^{\prime}$, so by Observation 20, the cycle ${\mathcal{V}}$ is still the
same minimum cycle in the coloring $\beta^{\prime\prime}$. Since in the
coloring $\beta^{\prime}$, there is no edge colored $1$ or $5$ in
${\mathcal{U}}_{<u_{l-h}}$, the coloring $\beta^{\prime\prime}$ is also
${\mathcal{U}}_{<u_{l-h}}$-equivalent to $\beta^{\prime}$. So in the coloring
$\beta^{\prime\prime}$, the fan $X_{u}(3)$ still contains the vertex
$z^{\prime}$ which is now missing the color $1$, and thus $X_{u}(3)$ is not
entangled with ${\mathcal{V}}$. By Lemma 24, we have a contradiction. So the
vertex $z^{\prime}$ belongs to $K_{v}(1,5)$, and thus the vertex $z$ does not
belong to $K_{v}(1,5)$. We now swap the component $C_{1,5}=K_{z}(1,5)$, and
denote by $\beta^{\prime\prime}$ the coloring obtained after the swap. The
coloring $\beta^{\prime\prime}$ is also ${\mathcal{V}}$-equivalent to
$\beta^{\prime}$, so the fan ${\mathcal{V}}$ is a minimum cycle in the
coloring $\beta^{\prime\prime}$. Moreover, since
$5\in\beta({\mathcal{U}}_{<u_{l-h}})$, $5\not\in\beta({\mathcal{Y}})$. We also
have that $5\not\in\beta({\mathcal{X}})$, so in total, the coloring
$\beta^{\prime\prime}$ is
$({\mathcal{Y}}\cup{\mathcal{X}}\setminus\\{z\\})$-equivalent to the coloring
$\beta^{\prime}$. This means that in the coloring $\beta^{\prime\prime}$, the
fan $X_{u}(4)$ still contains the vertex $z$ which is now missing the color
$1$, so $X_{u}(4)_{\leqslant z}$ is a $({\mathcal{V}},u)$-independent subfan
avoiding $v$. We also have that the fan $X_{v}(4)$ is now a path containing
the vertex $z$, so by Lemma 34 we have a contradiction.

######  Subcase 53.1.2 ($5\in\beta({\mathcal{U}}_{\geqslant u_{l-h}})$).

Let $s$ be such that $m(u_{l-s})=5$. The fan $X_{v}(5)$ is a saturated cycle
containing $u_{l-s}$, so the vertex $u_{l-s}$ belongs to the component
$K_{v}(1,5)$, and the vertex $z$ does not belong to this component. We now
swap the component $K_{z}(1,5)$ and denote by $\beta^{\prime\prime}$ the
coloring obtained after the swap. Since the color $5$ is not in
$\beta(X_{v}(4))$, the coloring $\beta^{\prime\prime}$ is
$(X_{v}(4)\setminus\\{z\\})$-equivalent to $\beta^{\prime}$. So in the
coloring $\beta^{\prime\prime}$, the fan $X_{v}(4)$ still contains the vertex
$z$ which is missing the color $1$, so it is now a path. Since the color $5$
is in $\beta({\mathcal{U}}_{>u_{l-h}})$, it is not in $\beta({\mathcal{Y}})$,
so the coloring $\beta^{\prime\prime}$ is
$(X_{u}(4)\setminus\\{z\\})$-equivalent to $\beta^{\prime}$, and thus
$X_{u}(4)$ still contains the vertex $z$. So the subfan $X_{u}(4)_{\leqslant
z}$ is now a $({\mathcal{V}},u)$-independent subfan avoiding $v$. By Lemma 34,
the fan $X_{v}(4)$ is a path not containing $z$; a contradiction.

######  Subcase 53.1.3 ($5\in\beta({\mathcal{Y}})$).

Let $z^{\prime}$ be the vertex of ${\mathcal{Y}}$ missing the color $5$ in the
coloring $\beta$. The vertices $z$ and $z^{\prime}$ are both missing the color
$5$ in the coloring $\beta^{\prime}$, so at least one of them is not in
$K_{v}(1,5)$. If the vertex $z$ is not in $K_{v}(1,5)$, then we swap the
component $C_{1,5}=K_{z}(1,5)$, and denote by $\beta^{\prime\prime}$ the
coloring obtained after the swap. The coloring $\beta^{\prime\prime}$ is
${\mathcal{V}}$-equivalent to $\beta^{\prime}$, so the cycle ${\mathcal{V}}$
is the same minimum cycle in the coloring $\beta^{\prime\prime}$ by
Observation 20.

If the vertex $u$ does not belong to $C_{1,5}$, then the fan $X_{u}(5)$ now
contains the vertex $z$ which is missing the color $1$. Thus
$X_{u}(5)_{\leqslant z}$ is now a $({\mathcal{V}},u)$-independent subfan
avoiding $v$, and by Lemma 34, the fan $X_{v}(5)$ is a path. However,
$\beta^{\prime\prime}(uu_{l-h})=\beta(uu_{l-h})=1$, and the property $P(j)$ is
true for all $j\leqslant h$, so by Lemma 52, there is no path around $v$. This
is a contradiction.

So the vertex $u$ belogns to $C_{1,5}$, and now $X_{u}(1)$ contains the vertex
$z$ which is missing the color $1$. So $X_{u}(1)$ is not entangled with
${\mathcal{V}}$, and by Lemma 24, we also have a contradiction.

######  Case 53.2 ($5\in\beta({\mathcal{X}})$).

Let $z^{\prime}$ be the vertex of ${\mathcal{X}}$ missing the color $5$ in the
coloring $\beta$.

######  Subcase 53.2.1 ($5\in\beta({\mathcal{U}}_{<u_{l-h}})$).

Let $z^{\prime\prime}$ be the vertex of ${\mathcal{U}}_{<u_{l-h}}$ missing the
color $5$ in the coloring $\beta$. Note that we may have
$z^{\prime\prime}=z^{\prime}$. The vertices $z$ and $z^{\prime\prime}$ are
both missing the color $5$ in the coloring $\beta^{\prime}$, so they are not
both part of $K_{v}(1,5)$. If $z^{\prime\prime}$ is not in $K_{v}(1,5)$, then
we swap $K_{z^{\prime\prime}}(1,5)$, and denote by $\beta^{\prime\prime}$ the
coloring obtained after the swap. The coloring $\beta^{\prime\prime}$ is
${\mathcal{V}}$-equivalent to $\beta^{\prime}$, so by Observation 20, the
cycle ${\mathcal{V}}$ is the same minimum cycle in the coloring
$\beta^{\prime\prime}$. Since there is no edge colored $1$ or $5$ in
$E({\mathcal{U}}_{\leqslant z^{\prime\prime}})$, the coloring
$\beta^{\prime\prime}$ is also ${\mathcal{U}}_{\leqslant
z^{\prime\prime}}$-equivalent to the coloring $\beta^{\prime}$, so $X_{u}(3)$
still contains the vertex $z^{\prime\prime}$ which is now missing the color
$1$, so it is not entangled with ${\mathcal{V}}$, by Lemma 24, this is a
contradiction.

So the vertex $z^{\prime\prime}$ belongs to $K_{v}(1,5)$, and thus the vertex
$z$ does not belong to this component. We swap the component
$C_{1,5}=K_{z}{1,5}$, and denote by $\beta^{\prime\prime}$ the coloring
obtained after the swap. In the coloring $\beta^{\prime\prime}$, the fan
$X_{v}(5)$ still contains the vertex $z$ which is missing the color $1$, so
this fan is now a path. If the vertex $u$ does not belong to $C_{1,5}$, then
$\beta^{\prime\prime}(uu_{l-h})=1$. Since the property $P(j)$ is true for all
$j\leqslant h$, there is no path around $v$, a contradiction. So the vertex
$u$ belongs to $C_{1,5}$. Now in the coloring $\beta^{\prime\prime}$, the fan
${\mathcal{U}}^{\prime}=X_{u}(3)=(uu^{\prime}_{1},\cdots,uu^{\prime}_{l^{\prime}})$
is smaller, but for any $j\leqslant h$, we still have that
$u_{l-j}=u^{\prime}_{l^{\prime}-j}\in V({\mathcal{U}}^{\prime})$. Note that we
have $z^{\prime\prime}=u^{\prime}_{l^{\prime}-h-1}$. So we have
${\mathcal{U}}^{\prime}=(uu^{\prime}_{1},\cdots,uu^{\prime}_{l-h-1}=uz^{\prime\prime},uu_{l-h},\cdots,uu_{l})$.
Since the property $P(j)$ is true for all $j\leqslant h$, the fan
$X_{v}(\beta(uu_{l-h}))=X_{v}(5)$ is a cycle, a contradiction.

######  Subcase 53.2.2 ($5\in\beta({\mathcal{U}}_{>u_{l-h}})$).

Let $s$ be such that $m^{\beta}(u_{l-s})=5$. In the coloring $\beta$, since
the property $P(s)$ is true, the fan $X_{v}(5)$ is a saturated cycle
containing $u_{s}$. But the color $5$ is in ${\mathcal{X}}$, so the fan
$X_{v}(5)$ also contains the vertex $z$, and thus $X_{v}(5)={\mathcal{X}}$. In
the coloring $\beta^{\prime}$, the fan $X_{v}(5)$ still contains the vertex
$z$ which is now missing the color $5$. Since the property $P(s)$ is true, the
cycle $X_{v}(5)$ is a a cycle containing the vertex $u_{l-s}$, so we have a
contradiction.

######  Subcase 53.2.3 ($5\in\beta({\mathcal{Y}})$).

Let $z^{\prime\prime}$ be the vertex of ${\mathcal{Y}}$ missing the color $5$
in the coloring $\beta$. Note that we may have $z^{\prime\prime}=z^{\prime}$.
Since the vertices $z$ and $z^{\prime\prime}$ are both missing the color $5$
in the coloring $\beta^{\prime}$, they are not both part of $K_{v}(1,5)$. If
$z$ is not in $K_{v}(1,5)$, then we swap the component $K_{z}(1,5)=C_{1,5}$
and denote by $\beta^{\prime\prime}$ the coloring obtained after the swap. The
coloring $\beta^{\prime\prime}$ is ${\mathcal{V}}$-equivalent to
$\beta^{\prime}$, so by Observation 20, the cycle ${\mathcal{V}}$ is the same
minimum cycle in the coloring $\beta^{\prime\prime}$. Moreover, the coloring
$\beta^{\prime\prime}$ is also $(X_{v}(5)\setminus\\{z\\})$-equivalent to
$\beta^{\prime}$, so this fan is now a path containing $z$.

If the vertex $u$ does not belong to $C_{1,5}$, then the coloring
$\beta^{\prime\prime}$ is $(X_{u}(5)\setminus\\{z\\})$-equivalent to
$\beta^{\prime}$, and thus $X_{u}(5)$ still contains the vertex $z$ which is
now missing the color $1$. So the subfan $X_{u}(<)_{\leqslant z}$ is now a
$({\mathcal{V}},u)$-independent subfan avoiding $v$, and it also contains $z$,
by Lemma 34, the fan $X_{v}(5)$ is a path that does not contain $z$, a
contradiction.