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

######  Subcase 53.2.4
($5\not\in(\beta({\mathcal{Y}})\cup\beta({\mathcal{U}}))$).

The vertices $z$ and $z^{\prime}$ are both missing the color $5$, so at least
one of them is not in $K_{v}(1,5)$.

If the vertex $z$ is not in $K_{v}(1,5)$, since $P(j)$ is true for all
$j\leqslant h$, then for all $j\leqslant h$, the vertex $z$ is not in
$X_{v}(\beta(uu_{l-j}))$. We now swap the component $C_{1,5}=K_{z}(1,5)$ to
obtain a coloring $\beta^{\prime\prime}$ where the subfan $X_{u}(4)$ is now a
$({\mathcal{V}},u)$-independent subfan avoiding $v$. 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}$. By Lemma 34, the fan $X_{v}(4)$ is now a path that
does not contain $z$. Since for all $j\leqslant h$, $P(j)$ is true and $z$
does not belong to $X_{v}(\beta(uu_{l-j})$, the coloring
$\beta^{\prime\prime}$ is also
$(\bigcup\limits_{j\in[0,h]}X_{v}(\beta(uu_{l-j})))$-equivalent to the
coloring $\beta^{\prime}$.

If the vertex $u$ does not belong to $C_{1,5}$, then the coloring
$\beta^{\prime\prime}$ is also ${\mathcal{U}}$ equivalent to the coloring
$\beta^{\prime}$. The edge $uu_{l-h}$ is still colored $1$, and the property
$P(j)$ is true for all $j\leqslant h$. By Lemma 52 there is no path around
$v$, a contradiction. So the vertex $u$ belongs to the component $C_{1,5}$,
and the edge $uu_{l-h}$ is now colored $5$. Let
${\mathcal{U}}^{\prime}=X^{\beta^{\prime\prime}}_{u}(3)=(uu^{\prime}_{1},\cdots,uu^{\prime}_{l^{\prime}})$.
Since $z\not\in X_{v}(\beta(uu_{l-j}))$ for all $j\leqslant h$, the coloring
$\beta^{\prime\prime}$ is
$(\bigcup\limits_{j\in[0,h]}X_{v}(\beta(uu_{l-j})))$-equivalent to the
coloring $\beta^{\prime}$, and it is also
${\mathcal{U}}_{>u_{l-h}}$-equivalent to the coloring $\beta^{\prime}$, so by
Lemma 51, for all $j\leqslant h$, we have $u^{\prime}_{l-j}=u_{l-j}$. In
particular, $u^{\prime}_{l-h}=u_{l-h}$. The coloring $\beta^{\prime\prime}$ is
$X_{u}(5)_{<z}$-equivalent to the coloring $\beta^{\prime}$, so in the
coloring $\beta^{\prime\prime}$, the fan $X_{u}(5)$ still contains the vertex
$z$ which is now missing the color $1$, therefore the fan $X_{u}(5)$ is a
path. Since $P(h)$ is true, we have a contradiction.

So the vertex $z$ belongs to $K_{v}(1,5)$, and the vertex $z^{\prime}$ does
not belong to this component. We now swap the component
$C_{1,5}=K_{z^{\prime}}(1,5)$, and obtain a coloring $\beta^{\prime\prime}$
that is ${\mathcal{V}}$-equivalent to $\beta^{\prime}$. By Observation 20, the
fan ${\mathcal{V}}$ is the same minimum cycle in the coloring
$\beta^{\prime\prime}$. Since the property $P(j)$ is true for all $j\leqslant
h$, and $z^{\prime}$ is not in $K_{v}(1,5)$, then for all $j\leqslant h$, the
vertex $z^{\prime}$ is not in $X_{v}(\beta(uu_{l-j}))$, and the coloring
$\beta^{\prime\prime}$ is
$(\bigcup\limits_{j\in[0,h]}X_{v}(\beta(uu_{l-j})))$-equivalent to the
coloring $\beta^{\prime}$. In the coloring $\beta^{\prime\prime}$, the fan
$X_{v}(4)$ is now a path, so similarly to the previous case, the vertex $u$
belongs to the component $C_{1,5}$. Therefore, in the coloring
$\beta^{\prime\prime}$, the edge $uu_{l-h}$ is colored $5$.

Let
${\mathcal{U}}^{\prime}=(uu^{\prime}_{1},\cdots,uu^{\prime}_{l^{\prime}})$.
Since the coloring $\beta^{\prime\prime}$ is
$(\bigcup\limits_{j\in[0,h]}X_{v}(\beta(uu_{l-j})))$-equivalent to the
coloring $\beta^{\prime}$, by Lemma 51, for any $j\leqslant h$ we have
$u^{\prime}_{l^{\prime}-j}=u_{l-j}$. The coloring $\beta^{\prime\prime}$ is
${\mathcal{U}}_{\leqslant v}$ equivalent to $\beta^{\prime}$, so $v$ is in
${\mathcal{U}}^{\prime\prime}$, and thus we have
$X_{u}(1)=X_{u}(5)={\mathcal{U}}^{\prime}$. So there exists a vertex
$z^{\prime\prime}$ missing the color $5$ in the fan $X_{u}(1)$. Note that
since $m(z^{\prime})=1$ and $m(z^{\prime\prime})=5$ we have $z\neq
z^{\prime\prime}$, however, we may have $z^{\prime\prime}=z$, and in this case
there exists a vertex in $X_{u}(1)$ missing a color in
$\beta(X_{u}(4)_{\leqslant z})$. We now have to distinguish the cases.

######  Subsubcase 53.2.4.1 ($z^{\prime\prime}\neq z$).

We consider the coloring $\beta^{\prime}$. In this coloring, the vertex
$z^{\prime\prime}$ is in $X_{u}(5)$ since $u$ is in $C_{1,5}$. If the vertex
$z^{\prime\prime}$ also belongs to $C_{1,5}$, then now $X_{u}(5)_{\leqslant
z^{\prime\prime}}$ is a subfan avoiding $v$. If there is en edge
$uu^{\prime\prime}$ in $E(X_{u}(5)_{\leqslant z^{\prime\prime}})$ colored with
a color in $\beta^{\prime}({\mathcal{V}})$ then the fan
$X_{u}(\beta^{\prime}(uu^{\prime\prime})))$ is not entangled with
${\mathcal{V}}$, and by Lemma 24 we have a contradiction. So the subfan
$X_{u}(5)_{\leqslant z^{\prime\prime}}$ is a $({\mathcal{V}},u)$-independent
subfan avoiding $v$. By Lemma 34 the fan $X_{v}(5)$ is a path, however, in the
coloring $\beta^{\prime}$ the fan $X_{v}(5)$ still contains the vertex $z$
that is misisng the color $5$, so $X_{v}(5)$ is a cycle, a contradiction.

So the vertex $z^{\prime\prime}$ does not belong to $C_{1,5}$, and thus is
still missing the color $5$ in the coloring $\beta^{\prime}$. We now swap the
component $K_{z^{\prime\prime}}(1,5)$ to obtain a coloring $\beta_{f}$ where
$X_{u}(5)_{\leqslant z^{\prime\prime}}$ is a $({\mathcal{V}},u)$-independent
subfan avoiding $v$, and where $X_{u}(5)$ is a cycle. Again by Lemma 34 we
have a contradiction.

######  Subsubcase 53.2.4.2 ($z^{\prime\prime}=z^{\prime}$).

So there exists a vertex $w$ in $X_{u}(5)$ such that
$m(w)\in\beta^{\prime}(X_{u}(4)_{\leqslant z})$ and $w\not\in
V(X_{u}(4)_{\leqslant z})$. We now need to distinguish whether or not
$m(w)=4$.

######  Subsubsubcase 53.2.4.2.1 ($m(w)\neq 4$).

In this case, without loss of generality, assume that $m(w)=6$, and let
$w^{\prime}$ be the vertex of $X_{v}(4)_{\leqslant z}$ missing the color $6$.
The vertices $w$ and $w^{\prime}$ are both misisng the color $6$, so they are
not both part of $K_{v}(1,6)$.

If $w^{\prime}$ is not in $K_{v}(1,6)$, then we swap
$C_{1,6}=K_{w^{\prime}}(1,6)$ to obtain a coloring $\beta^{\prime\prime}$
where $X_{u}(4)_{\leqslant w^{\prime}}$ is a $({\mathcal{V}},u)$-independent
subfan avoiding $v$. The coloring $\beta^{\prime\prime}$ is
${\mathcal{V}}$-equivalent to ${\mathcal{V}}$, so the fan ${\mathcal{V}}$ is
still the same minimum cycle in the coloring $\beta^{\prime}$ by Observation
20. So by Lemma 34 the fan $X_{v}(4)$ is a path that does not contain
$w^{\prime}$. If the vertex $u$ does not belong to $C_{1,6}$, then the
coloring $\beta^{\prime\prime}$ is ${\mathcal{U}}$-equivalent to
$\beta^{\prime}$, the property $P(j)$ is true for all $j\leqslant h$ and
$\beta^{\prime\prime}(uu_{l-h})=1$ so by Lemma 52 there is no path around $v$,
a contradiction.

So the vertex $u$ belongs to $C_{1,6}$, and we have
$\beta^{\prime\prime}(uu_{l-h})=6$. Let
${\mathcal{U}}^{\prime}=X_{u}^{\beta^{\prime\prime}}(3)=(uu^{\prime}_{1},\cdots,uu^{\prime}_{l^{\prime}})$.
The coloring $\beta^{\prime\prime}$ is
$(\bigcup\limits_{j\in[0,h]}X_{v}(\beta(uu_{l-j})))$-equivalent to the
coloring $\beta^{\prime}$ and is ${\mathcal{U}}_{>u_{l-h}}$-equivalent to the
coloring $\beta^{\prime}$ so by Lemma 51, for all $j\leqslant h$ we have
$u^{\prime}_{l^{\prime}-j}=u_{l-j}$. In the coloring $\beta^{\prime}$, the fan
$X_{v}(4)$ contains the vertex $z^{\prime}$ missing the color $5$, and the fan
$X_{v}(5)$ is a cycle that contains the vertex $z$, and in the coloring
$\beta^{\prime\prime}$, the fan $X_{u}(4)$ is a path. So there exists a vertex
$w^{\prime\prime}$ in $X_{v}(4)$ that is missing the color $6$ in the coloring
$\beta^{\prime}$ and that belongs to $C_{1,6}$. this vertex is now missing the
color $1$ in the coloring $\beta^{\prime\prime}$. If $w^{\prime\prime}$ is in
$X^{\beta^{\prime}}_{v}(4)_{\leqslant z^{\prime}}$, then the fan
$X_{v}^{\beta^{\prime\prime}}(6)$ is now a comet containing two vertices ($z$
and $z^{\prime}$) missing the color $5$. Since the property $P(h)$ is true, we
have a contradiction. So the vertex $w^{\prime\prime}$ si in
$X^{\beta^{\prime}}_{v}(5)$. But now, in the coloring $\beta^{\prime\prime}$,
the fan $X_{v}(6)$ contains the vertex $z$ which is still missing the color
$5$, and the fan $X_{v}(5)$ is a path, so the fan $X_{v}(6)$ is a path. Again
since $P(h)$ is true, we have a contradiction. So the vertex $w^{\prime}$
belongs to $K_{v}(1,6)$.

Therefore, the vertex $w$ does not belong to $K_{v}(1,6)$, and we swap the
component $C_{1,6}=K_{w}(1,6)$ to obtain a coloring $\beta^{\prime\prime}$
where $X_{u}(5)_{\leqslant w}$ is a subfan avoiding $v$. The coloring
$\beta^{\prime\prime}$ is ${\mathcal{V}}$-equivalent to the coloring
$\beta^{\prime}$, so by Observation 20, the fan ${\mathcal{V}}$ is the same
minimum cycle in the coloring $\beta^{\prime\prime}$. Similarly to the
previous case, the subfan $X_{u}(5)_{\leqslant w}$ is a
$({\mathcal{V}},u)$-independent subfan avoiding $v$, so $X_{v}(5)$ is a path,
and the vertex $u$ belongs to $C_{1,6}$. Since the vertex $z$ is still missing
the color $5$, it means that in the coloring $\beta^{\prime\prime}$ the fan
$X_{u}(1)$ now contains the vertex $w$ which is missing the color $1$, and so
it is not entangled with ${\mathcal{V}}$. By Lemma 24 we have a contradiction.

######  Subsubsubcase 53.2.4.2.2 ($m(w)=4$).

Since the fan ${\mathcal{Y}}=X_{z}(5)$ is a path in the coloring $\beta$, the
fan $X_{z}(4)$ is a path in the coloring $\beta^{\prime}$. In the coloring
$\beta^{\prime}$ we invert the path $X_{z}(5)$ until we reach a coloring where
$m(z)\in\beta^{\prime}(X_{u}(5)_{\leqslant w})$ and denote by
$\beta^{\prime\prime}$ the coloring obtained after the inversion. Note that
since $4\in\beta^{\prime}(X_{z}(5))\cap\beta(X_{u}(5)_{\leqslant w})$ the
inversion is well defined. The coloring $\beta^{\prime\prime}$ is
${\mathcal{V}}$-equivalent to $\beta^{\prime}$ so the fan ${\mathcal{V}}$ is
the same minimum cycle in the coloring $\beta^{\prime\prime}$. The coloring
$\beta^{\prime\prime}$ is also ${\mathcal{U}}$-equivalent to $\beta^{\prime}$,
so $X_{u}^{\beta^{\prime\prime}}(3)={\mathcal{U}}$ and since $P(j)$ is true
for all $j\leqslant h$, the fan $X_{v}(\beta^{\prime\prime}(uu_{l-j}))$ is a
saturated cycle if $\beta^{\prime\prime}(uu_{l-j})\neq 1$. The coloring
$\beta^{\prime\prime}$ is $(X_{v}(4)\setminus\\{z\\})$-equivalent to
$\beta^{\prime}$, so the fan $X_{v}(4)$ still contains the vertex $z^{\prime}$
which is missing $5$, and the vertex $z$. Finally, the coloring
$\beta^{\prime\prime}$ is $X_{u}(5)_{\leqslant w}$-equivalent to the coloring
$\beta^{\prime}$. Let $c_{z}$ be the missing color of $z$ in
$\beta^{\prime\prime}$, and let $w^{\prime}$ be the vertex of
$X_{u}(5)_{\leqslant w}$ missing the color $c_{z}$. Note that is $c_{z}=4$,
then we have $w^{\prime}=w$.

The proof is similar to the previous case, and we now consider the components
of $K(1,c_{z})$. The vertices $z$ and $w^{\prime}$ are both missing the color
$c_{z}$ so at least of them is not in $K_{v}(1,c_{z})$. If the vertex $z$ is
not in $K_{v}(1,c_{z})$, then we swap the component
$C_{1,c_{z}}=K_{z}(1,c_{z})$ to obtain a coloring $\beta_{f}$ that is
${\mathcal{V}}$-equivalent to $\beta^{\prime\prime}$. By Observation 18 the
fan ${\mathcal{V}}$ is the same minimum cycle in the coloring $\beta_{f}$, and
now $X_{u}(4)_{\leqslant z}$ is a $({\mathcal{V}},u)$-independent subfan
avoiding $v$, so by Lemma 34 the fan $X_{v}(4)$ is now a path not containing
$z$. Note that the coloring $\beta_{f}$ is also
$(\bigcup\limits_{j\in[0,h]}X_{v}(\beta(uu_{l-j})))$-equivalent to the
coloring $\beta^{\prime\prime}$. If the vertex $u$ does not belong to
$C_{1,c_{z}}$, then the coloring $\beta_{f}$ is ${\mathcal{U}}$-equivalent to
$\beta^{\prime\prime}$, and in particular $\beta_{f}(uu_{l-h})=1$. Since
$P(j)$ is true for all $j\leqslant h$, by Lemma 52 there is no path around
$v$, a contradiction.

So the vertex $u$ belongs to $C_{1,c_{z}}$, and now $\beta_{f}(uu_{l-h})=6$.
Since the fan $X_{v}(4)$ is now a path that does not contain $z$, it means
that in the coloring $\beta^{\prime\prime}$ there is a vertex
$w^{\prime\prime}$ in $X_{v}(4)$ which is missing the color $c_{z}$ and which
also belongs to $C_{1,c_{z}}$. It means that in the coloring $\beta_{f}$, the
fan $X_{v}(c_{z})$ is now a path containing $z$. Let
${\mathcal{U}}^{\prime}=X_{u}^{\beta_{f}}(3)=(uu^{\prime}_{1},\cdots,uu^{\prime}_{l^{\prime}})$.
The coloring $\beta_{f}$ is ${\mathcal{U}}_{>u_{l-h}}$-equivalent to
$\beta^{\prime\prime}$ and is also
$(\bigcup\limits_{j\in[0,h]}X_{v}(\beta(uu_{l-j})))$-equivalent to
$\beta^{\prime\prime}$, so for all $j\leqslant h$, we have
$u^{\prime}_{l^{\prime}-j}=u_{l-j}$ by Lemma 51. In particular
$u^{\prime}_{l-h}=u_{l-h}$. Since $P(h)$ is true, and
$\beta_{f}(uu^{\prime}_{l^{\prime}-h})=c_{z}$, the fan $X_{v}(c_{z})$ is a
cycle, a contradiction.

So the vertex $z$ belongs to $K_{v}(1,c_{z})$ and the vertex $w^{\prime}$ does
not belong to this component. We now swap the component
$C_{1,c_{z}}=K_{w}(1,c_{z})$ and denote by $\beta_{f}$ the coloring obtained
after the swap. The coloring $\beta_{f}$ is ${\mathcal{V}}$-equivalent to
$\beta^{\prime\prime}$ so by Observation 18 the fan ${\mathcal{V}}$ is the
same minimum cycle in the coloring $\beta_{f}$. The coloring $\beta_{f}$ is
also $(\bigcup\limits_{j\in[0,h]}X_{v}(\beta(uu_{l-j})))$-equivalent to the
coloring $\beta^{\prime\prime}$. In the coloring $\beta_{f}$ the subfan
$X_{u}(5)_{\leqslant w^{\prime}}$ is now a subfan avoiding $v$. If there is an
edge $uu^{\prime\prime}$ in $E(X_{u}(5)_{\leqslant w^{\prime}})$ colored with
a color in $\beta_{f}({\mathcal{V}})$, then
$X_{u}(\beta_{f}(uu^{\prime\prime}))$ is not entangled with ${\mathcal{V}}$
and by Lemma 24 we have a contradiction. So the subfan $X_{u}(5)_{\leqslant
w^{\prime}}$ is a $({\mathcal{V}},u)$-independent subfan avoiding $v$ and thus
by Lemma 34 the fan $X_{v}(5)$ is now a path that does not contain
$w^{\prime}$. Similarly to the previous case, this means that the vertex $u$
belongs to the component $C_{1,c_{z}}$, and thus that
$\beta_{f}(uu_{l-h})=c_{z}$. The fan $X_{v}(5)$ still contains the vertex $z$
which is missing the color $c_{z}$, and the fan $X_{v}(5)$ is a path, so the
fan $X_{v}(c_{z})$ is a path. Let
${\mathcal{U}}^{\prime}=X^{\beta_{f}}_{u}(3)=(uu^{\prime}_{1},\cdots,uu^{\prime}_{l^{\prime}})$.
Since $P(j)$ is true for all $j\leqslant h$ and since the coloring $\beta_{f}$
is $(\bigcup\limits_{j\in[0,h]}X_{v}(\beta(uu_{l-j})))$-equivalent to the
coloring $\beta^{\prime\prime}$, by Lemma 51 for $j\leqslant h$, we have
$u^{\prime}_{l^{\prime}-j}=u_{l-j}$. In particular,
$u^{\prime}_{l-h}=u_{l-h}$. The edge $uu^{\prime}_{l^{\prime}-h}$ is now
colored $c_{z}$ and the property $P(h)$ is true, so the fan $X_{v}(c_{z})$ is
a cycle. This is a contradiction.

∎

Before proving the induction step of the proof we need to introduce a new
property implied by $P(i)$.

###  4.5 The property $Q(i)$

######  Definition 54.

Let $i\geqslant 0$, we define the property $Q(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 for any color $c\in\beta({\mathcal{V}})$, the
fan $X_{u_{l-i-1}}(c)$ is a cycle entangled with ${\mathcal{V}}$ and
${\mathcal{U}}_{\geqslant u_{l-i-2}}$.

We now prove that the property $Q(i)$ is implied by the property $P(i)$. And
we first prove th following lemma concerning saturated cycles around the
centrel vertex of a minimum cycle.

######  Lemma 55.

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}}$ and ${\mathcal{W}}=(vw_{1},\cdots,vw_{t})$ a saturated cycle
around $v$. Then the fans ${\mathcal{W}}$ and
${\mathcal{U}}=X_{u}(m(u^{\prime}))$ are entangled.

###### Proof.

By Lemma 24, the fan ${\mathcal{U}}$ is a cycle entangled with
${\mathcal{V}}$, so if ${\mathcal{W}}={\mathcal{V}}$, the fans ${\mathcal{W}}$
and ${\mathcal{U}}$ are entangled as desired. So assume that
${\mathcal{W}}\neq{\mathcal{V}}$ and that ${\mathcal{W}}$ is not entangled
with ${\mathcal{U}}$. Without loss of generality, we assume that the vertices
$v$, $u$ and $u^{\prime}$ are respectively missing the colors $1$, $2$, and
$3$. Since ${\mathcal{W}}\neq{\mathcal{V}}$ and ${\mathcal{W}}$ is centered at
$v$, we have that $\beta({\mathcal{W}})\cap\beta({\mathcal{V}})=\\{1\\}$.
Since ${\mathcal{W}}$ and ${\mathcal{U}}$ are not entangled, there exists
$c\in\beta({\mathcal{U}})\cap\beta({\mathcal{W}})$ such that
$M({\mathcal{U}},c)\neq M({\mathcal{W}},c)$. Without loss of generality, since
$c\not\in\\{1,2,3\\}$, we assume that $c=4$ and that
$u_{i}=M({\mathcal{U}},4)$ is the first such vertex in ${\mathcal{U}}$; up to
shifting the indices in ${\mathcal{W}}$, we also assume that $m(w_{t})=4$, and
thus that ${\mathcal{W}}=X_{v}(4)$.

Since the cycle ${\mathcal{W}}$ is saturated, the vertex $w_{t}$ belongs to
$K_{v}(1,4)$, so the vertex $z$ does not belong to $K_{v}(1,4)$. We swap the
component $C_{1,4}=K_{z}(1,4)$ and denote by $\beta_{2}$ the coloring obtained
after the swap.

If $u\not\in C_{1,4}$, or there is no edge colored $1$ in
${\mathcal{U}}_{<i}$, then the coloring $\beta_{2}$ is
$({\mathcal{V}}\cup{\mathcal{W}}\cup{\mathcal{U}}_{<i})$-equivalent to
$\beta$. Hence, in the coloring $\beta_{2}$, the fan ${\mathcal{V}}$ is a
minimum cycle by Observation 20, but now the fan
$X_{u}(m(u^{\prime})=(uu_{1},\cdot,uu_{i})$ is now a path, by Lemma 24, this
is a contradiction.

So $u\in C_{1,4}$, and there is an edge colored $1$ in ${\mathcal{U}}_{<i}$.
Since by Lemma 24, the cycle ${\mathcal{U}}$ is entangled with
${\mathcal{V}}$, the edge $uv_{j-1}$ and the edge $uv$ are in
$E({\mathcal{U}})$. We denote by $x$ the vertex connected to $u$ y the edge
colored $1$ and by $c_{j-1}$ the missing color of $v_{j-1}$ in $\beta$. Note
that we may have $v_{j-1}=u^{\prime}$, and thus $c_{j-1}=2$. The fan
${\mathcal{U}}$ is of the form
$(uu_{1},\cdots,uv_{j-1},uv,ux,\cdots,uu_{i},\cdots,uu^{\prime})$. The
coloring $\beta_{2}$ is $({\mathcal{V}})$\- equivalent to $\beta$, so by
Observation 20, the cycle ${\mathcal{V}}$ is a minimum cycle in $\beta_{2}$.
But now the fan $X_{u}(4)$ is a comet where $v$ and $u_{i}$ are missing the
same color $1$, more precisely,
$X_{u}(4)=(ux,\cdots,uu_{i},\cdots,uu^{\prime},uu_{1},\cdots,uv_{j-1},uv)$.
Note that $X_{u}(3)$ is a cycle which is a subsequence of $X_{u}(4)$. If there
is an edge colored with a color $c\in\beta({\mathcal{V}})$ in $X_{u}(4)$
between the edges $ux$ and $uu_{i}$, then the fan $X_{v}(c)$ is a comet, which
is a contradiction by Lemma 24.

So there is no edge colored with a color $c\in\beta({\mathcal{V}})$ in
$X_{u}(4)$ between the edges $ux$ and $uu_{i}$. Since the fan ${\mathcal{V}}$
is a minimum cycle, it is saturated by Lemma 15, so $u\in K_{v}(1,2)$, and
thus $u_{i}\not\in K_{v}(1,2)$. We now swap the component $K_{u_{i}}(1,2)$ to
obtain a coloring $\beta_{3}$. The coloring $\beta_{3}$ is
$({\mathcal{V}}\cup{\mathcal{W}})$-equivalent to $\beta_{2}$, so the fan
${\mathcal{V}}$ is a minimum cycle in $\beta_{3}$ by Observation 20.

We now show that ${\mathcal{V}}$ is invertible in the coloring $\beta_{3}$.
The cycle ${\mathcal{V}}$ is tight by Observation 21, so the vertex $u$
belongs to the component $C_{2,j-1}=K_{v_{j-1}}(2,c_{j-1})$, thus the edges
$vu$ and $vv_{j+1}$ also belong to $C_{2,j-1}$. In the coloring $\beta_{3}$,
the fan $X_{u}(4)$ is now a path that we invert until we reach a coloring
$\beta_{4}$ where $m(u)\in\beta({\mathcal{W}})$. Note that since
$4\in\beta({\mathcal{W}})$, the inversion is well-defined and moreover, since
$\beta_{3}$ is also $({\mathcal{W}})$-equivalent to $\beta$, we have
$\beta_{3}({\mathcal{W}})=\beta({\mathcal{W}})$. Since
$u\not\in{\mathcal{W}}$, by Observation 17, the coloring $\beta_{4}$ is
$({\mathcal{W}})$-equivalent to $\beta_{3}$, so ${\mathcal{W}}$ is still the
same cycle in $\beta_{4}$. Moreover, since
$\beta_{3}(X_{u}(4))\cap\beta_{3}({\mathcal{V}})=\\{2\\}$, the coloring
$\beta_{4}$ is $({\mathcal{V}}\setminus\\{u\\}\cup C_{2,j-1})$-equivalent to
$\beta_{3}$.

We denote by $w_{s}$ the vertex of ${\mathcal{W}}$ such that
$m^{\beta_{4}}(u)=m^{\beta_{4}}(w_{s})$, and we denote by $c_{s}$ this missing
color. Note that we may have that $w_{t}=w_{s}$, and thus $c_{s}=4$. The
vertices $u$ and $w_{s}$ are missing the same color $c_{s}$, so they are not
both part of the component $K_{v}(1,c_{s})$ and we now have to distinguish the
cases.

######  Case 55.1 ($u\not\in K_{v}(1,c_{s})$).

In this case, we swap the component $C_{1,c_{s}}=K_{u}(1,c_{s})$ and obtain a
coloring that we denote by $\beta_{5}$. Since $\\{1,c_{s},2,c_{j-1}\\}=4$, the
coloring $\beta_{5}$ is $(C_{2,j-1})$-equivalent to $\beta_{4}$, so it is
$(C_{2,j-1})$-equivalent to $\beta_{3}$. In the coloring $\beta_{5}$, the
vertex $u$ is now missing the color $1$, so the fan
$X_{v}(m(u))=(vv_{j+1},\cdots,vv_{j-1},vu)$ is now a path that we invert, we
denote by $\beta_{6}$ the coloring obtained after the inversion. In the
coloring $\beta_{6}$, the vertices $v_{j+1}$ and $v$ are missing the color
$2$, and the vertex $u$ is missing the color $c_{j-1}$. So now the component
$C^{\prime}_{2,j-1}=K_{v_{j^{\prime}-1}}$ is exactly
$C_{2,j-1}\cup\\{vv_{j-1}\\}\setminus\\{vu,vv_{j+1}\\}$ and we swap it. After
this swap, the vertices $v$ and $u$ are missing the same color $c_{j-1}$, and
the edge $uv$ is colroed $1$; we swap this edge and we denote by $\beta_{7}$
the coloring obtained after the swap. In the coloring $\beta_{7}$, the vertex
$u$ is missing the color $1$, so the component $K_{u}(1,c_{s})$ is now exactly
$C_{1,c_{s}}$, so we swap back this component. Note that since
$\\{1,2,c_{s},c_{j-1}\\}=4$, we can swap back $C_{1,c_{s}}$ before
$C^{\prime}_{2,j-1}$. In the coloring obtained after the swap, the fan
$X_{u}(2)$ is now a path that we invert, and we denote by $\beta_{8}$ the
coloring obtained after the inversion. In the coloring $\beta_{8}$, the vertex
$u$ is now missing the color $2$, so the component $K_{v_{j-1}}(2,c_{j-1})$ is
now exactly $C^{\prime}_{2,j-1}\cup\\{uv\\}$. After swapping back this
component we obtain exactly ${\mathcal{V}}^{-1}(\beta_{3})$, a contradiction.

######  Case 55.2 ($u\in K_{v}(1,c_{s})$).

The principle in the same as in the previous case, but instead of changing the
missing color of $u$, we will change the missing of of $v$ using the fan
$X_{v}(c_{s})$ to transform ${\mathcal{V}}$ into a path. As $u$ belongs to
$K_{v}(1,c_{s})$, the vertex $w_{s}$ does not belong to this component. So we
swap the component $C_{1,c_{s}}=K_{w_{s}}(1,c_{s})$ to obtain a coloring where
$X_{v}(c_{s})$ is now a path that we invert; we denote by $\beta_{5}$ the
coloring obtained after the inversion. Note that since $X_{v}(c_{s})$ was a
cycle in $\beta_{4}$, we have
$\beta_{4}(X_{v}(c_{s}))\cap\beta_{4}({\mathcal{V}})=\\{1\\}$,and so
$\\{2,c_{j-1}\\}\cap\beta_{4}(X_{v}(c_{s}))=\emptyset$. Hence the coloring
$\beta_{5}$ is $(C_{2,j-1})$-equivalent to the coloring $\beta_{4}$. In the
coloring $\beta_{5}$, the fan $X_{v}(2)=(vv_{j+1},\cdots,vu)$ is now a path
that we invert, and we denote by $\beta_{6}$ the coloring obtained after the
swap. Similarly to the previous case, in the coloring $\beta_{6}$, the
vertices $v$ and $v_{j+1}$ are missing the color $2$, and the vertex $u$ is
missing the color $c_{j-1}$. So in the coloring $\beta_{6}$, the component
$C^{\prime}_{2,j-1}=K_{v_{j-1}}(2,c_{j-1})$ is exactly
$C_{2,j-1}\cup\\{vv_{j-1}\\}\setminus\\{vv_{j^{\prime}+1},vu\\}$, and we swap
it to obtain a coloring where the vertices $u$ and $v$ are missing the color
$c_{j-1}$ and where the edge $uv$ is colored $c_{s}$. After swapping the edge
$uv$, we obtain a coloring where, the fan $X_{v}(1)$ is now a path that we
invert, we denote by $\beta_{7}$ the coloring obtained after the inversion. In
the coloring $\beta_{7}$, the component $K_{w_{s}}(1,c_{s})$ is exactly
$C_{1,c_{s}}$ and we swap back this component. Note that since
$|\\{1,2,c_{s},c_{j-1}\\}|=4$, we can swap back this component before
$C^{\prime}_{2,j-1}$. In the coloring obtained after the swap, the fan
$X_{u}(2)$ is now a path that we invert, we denote by $\beta_{8}$ the coloring
obtained after the swap. In the coloring $\beta_{8}$, the vertex $u$ is now
missing the color $2$, so the component $K_{v_{j-1}}(2,c_{j-1})$ is now
exactly $C^{\prime}_{2,j-1}\cup\\{vu\\}$ and we swap back this component to
obtain ${\mathcal{V}}^{-1}(\beta_{3})$ as desired.

∎

######  Lemma 56.

Let $i\geqslant 0$, if $P(i)$ is true for all $j\leqslant i$, then $Q(j)$ is
true for all $j\leqslant i$.

###### Proof.

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 assume that
$P(j)$ is true for all $j\leqslant i$. Without loss of generality, we assume
that the vertices $v$, $u$ and $u^{\prime}$ are respectively missing the
colors $1$, $2$, and $3$. Let $t\leqslant i$, and $z=u_{l-t-1}$. We prove that
$Q(t)$ is true.

######  Claim 57.

The vertex $z$ is not missing a color in $\beta({\mathcal{V}})$.

###### Proof.

Otherwise, assume that $m(z)\in\beta({\mathcal{V}})$. The fan ${\mathcal{V}}$
is a minimum cycle in $\beta$ so by Lemma 24, then fan ${\mathcal{U}}$ is a
cycle entangled with ${\mathcal{V}}$.

If $m(z)\neq 1$, then since ${\mathcal{U}}$ is a cycle entangled with
${\mathcal{V}}$ by Lemma 24, we have $z\in V({\mathcal{V}})$ so by Lemma 24
for any color $c\in\beta({\mathcal{V}})$, $X_{z}(c)$ is a cycle entangled with
${\mathcal{V}}$. Moreover, since the property $P(t)$ is true, so
$X_{v}(\beta(uz))=(vw_{1},\cdots,w_{x})$ is a saturated cycle, and by Lemma 55
is is entangled with ${\mathcal{U}}=X_{u}(m(u^{\prime}))$ and
$X_{z}(m(u))=(zz_{1},\cdots,zz_{r})$, and thus $u_{l-t-2}=w_{x}=z_{r-1}$, so
$Q(t)$ is true.

If $m(z)=1$, then since ${\mathcal{U}}$ is entangled with ${\mathcal{V}}$, we
have $z=v$. So for any $c\in\beta({\mathcal{V}})$, $X_{z}(c)={\mathcal{V}}$
and thus is a cycle entangled with ${\mathcal{V}}$. Moreover, this means that
$\beta(uz)=\beta(uv)$ and thus $m(u_{l-t-2})=\beta(uv)$, so $u_{l-t-2}$ is the
vertex just before $u$ in the cycle ${\mathcal{V}}$. By definition of
${\mathcal{V}}$, the fan $X_{z}(m(u)$ contains this vertex, and thus $Q(t)$ is
true. In both cases, we have a contradiction. ∎

######  Claim 58.

There is no edge in $E({\mathcal{U}}_{>z})$ colored with a color
$beta({\mathcal{V}})$.

###### Proof.

We first prove that there is no vertex in
$V({\mathcal{U}}_{>z})\setminus\\{u^{\prime}\\}$ missing a color
$c\in\beta({\mathcal{V}})$. Otherwise, assume that there exists such a vertex
$z^{\prime}$. The cycle ${\mathcal{V}}$ is minimum in $\beta({\mathcal{V}})$,
so by Lemma 24, the fan ${\mathcal{U}}$ is entangled with ${\mathcal{V}}$. If
$c\neq 1$, then $z^{\prime}\in V({\mathcal{V}})$. By Lemma 24, the fan
${\mathcal{U}}^{\prime}=X_{u}(m(z^{\prime}))=(uu^{\prime}_{1},\cdots,uu^{\prime}_{l^{\prime}})$
is a cycle entangled with ${\mathcal{V}}$, so
$u^{\prime}_{l^{\prime}}=z^{\prime}$ and
$V({\mathcal{U}})=V({\mathcal{U}}^{\prime})$. Thus there exists $t^{\prime}<t$
such that $z=u{l^{\prime}-t^{\prime}-1}$. Since $t$ is minimum,
$Q(t^{\prime})$ is true, and thus $Q(t)$ is true.

If $c=1$, then $z^{\prime}=v$ since ${\mathcal{U}}$ is entangled with
${\mathcal{V}}$, and $\beta(uz^{\prime})=\beta(uv)$. Let $z^{\prime\prime}$ be
the vertex just before $z^{\prime}$ in ${\mathcal{U}}$. Since
$\beta(uz^{\prime})=\beta(uv)$, then
$m(z^{\prime\prime})=\beta(uv)\in\beta({\mathcal{V}})$. Since
$m(z)\not\in\beta({\mathcal{V}})$, we have that $z^{\prime\prime}\neq z$. This
means that $z^{\prime\prime}$ is a vertex in
$V({\mathcal{U}}_{>z})\setminus\\{u^{\prime}\\}$ missing a color in
$\beta({\mathcal{V}})$, this is a contradiction. ∎

Let $c\in\beta({\mathcal{V}})$, we prove that
${\mathcal{Z}}=X_{z}(c)=(zz_{1},\cdots,zz_{r})$ is a cycle entangled with
${\mathcal{V}}$ and ${\mathcal{U}}_{\geqslant z}$.

By Claim 57 $m(z)\not\in\beta({\mathcal{V}})$, so without loss of generality,
we assume that $z$ is missing the color $4$. By Lemma 48 the fan
${\mathcal{Z}}$ is not a path. Before proving that ${\mathcal{Z}}$ is not a
comet, we first prove that is it entangled with ${\mathcal{V}}$ and
${\mathcal{U}}_{\geqslant u_{l-t-2}}$.

######  Proposition 59.

The fan ${\mathcal{Z}}$ is entangled with ${\mathcal{V}}$ and
${\mathcal{U}}_{\geqslant u_{l-t-2}}$.

###### Proof.

Otherwise, assume that there exists $s$ such that
$m(z_{s})\in\beta({\mathcal{V}})\cup\beta({\mathcal{U}}_{\geqslant z})$ and
$z_{s}\not\in V({\mathcal{V}})\cup V({\mathcal{U}}_{\geqslant z})$. Without
loss of generality, we assume that such an $s$ is minimum. We also assume that
there is no edge colored with a color in $\beta({\mathcal{V}})$ in
$E({\mathcal{Z}}_{[z_{2},z_{s-1}]})$. Otherwise, if such an edge $zz_{x}$
exists, is suffices to consider the fan
$X_{z}(\beta(zz_{x}))=(zz_{x},\cdots,zz_{s})$. We now have to distinguish the
cases.

######  Case 59.1 ($m(z_{s})=1$).

In this case, since, $P(t)$ is true, $X_{v}(4)$ is a saturated cycle
containing $z$, so $v\in K_{z}(1,4)$, and thus $z_{s}\not\in K_{z}(1,4)$. We
now swap the component $C_{1,4}=K_{z_{s}}(1,4)$, and denote by
$\beta^{\prime}$ the coloring obtained after the swap. In the coloring
$\beta^{\prime}$, the fan $X_{z}(c)$ is now a path. The coloring
$\beta^{\prime}$ is ${\mathcal{V}}$-equivalent to $\beta$, so ${\mathcal{V}}$
is still a minimum cycle in $\beta^{\prime}$. If the coloring $\beta^{\prime}$
is also ${\mathcal{U}}_{\leqslant z}$-equivalent to $\beta$ (i.e., $C_{1,4}$
does not contain $u$ or there is no edge colored $1$ in
${\mathcal{U}}_{\leqslant z}$), then $z$ is still a vertex of
${\mathcal{U}}=X_{u}(3)$, and the fan $X_{z}(c)$ is now a path, by Lemma 48
this is a contradiction. So the vertex $u$ belongs to $C_{1,4}$, and there is
an edge $uu_{h}$ colored $1$ in ${\mathcal{U}}_{<z}$. So in the coloring
$\beta^{\prime}$, the edge $uu_{h}$ is now colored $4$, and the edge $u_{l-t}$
is now colored $1$. The fan $X_{v}(4)$ is still a saturated cycle containing
$z$, but now the fan $X_{u}(4)$ is also a cycle containing $z$. In this
coloring the fan $X_{z}(c)$ is a path, so by Lemma 53, we have a
contradiction.

######  Case 59.2
($m(z_{s})=c^{\prime}\in\beta({\mathcal{V}})\setminus\\{1\\}$).

In this case, since ${\mathcal{V}}$ is minimum, it is saturated by Lemma 15,
thus $z_{s}\not\in K_{v}(1,c^{\prime})$. We now swap the component
$C_{1,c^{\prime}}=K_{z_{s}}(1,c^{\prime})$, and denote by $\beta^{\prime}$ the
coloring obtained after the swap. This coloring is ${\mathcal{V}}$-equivalent
to $\beta$, so ${\mathcal{V}}$ is still a minimum cycle in the coloring
$\beta^{\prime}$. By Claim 58, there is no edge with a color in
$\beta({\mathcal{V}})$ in ${\mathcal{U}}_{>z}$, so $\beta^{\prime}$ is
${\mathcal{U}}_{>z}$-equivalent to $\beta$. Moreover, let
${\mathcal{U}}^{\prime}=X^{\beta^{\prime}}_{u}(3)=(uu^{\prime}_{1},\cdots,uu^{\prime}_{l^{\prime}})$;
the coloring $\beta^{\prime}$ is also
$(\bigcup\limits_{j\in[0,t]}X_{v}(\beta(uu_{j})))$-equivalent to $\beta$ since
each of these fans are saturated cycles, and the vertex $z_{s}$ does not
belong to any of them. So by Lemma 51, in the coloring $\beta^{\prime}$, for
any $j\leqslant(t+1)$, $u^{\prime}_{l^{\prime}-j}=u_{l-j}$. In particular,
$u^{\prime}_{l^{\prime}-t-1}=u_{l-t-1}=z$. But now $X_{z}(c)$ is not entangled
with $\\{v\\}$ since it contains the vertex $z_{s}$ which is missing the color
$1$. This case is similar to the previous one.

######  Case 59.3 ($m(z_{s})=c^{\prime}\in\beta({\mathcal{U}}_{>z})$).

Let $u_{l-h}$ be the vertex of ${\mathcal{U}}_{>z}$ missing the color
$c^{\prime}$. In this case, since $P(j)$ is true for all $j\leqslant t$, the
fan $X_{v}(\beta(uu_{l-j}))$ is a saturated cycle. In particular, the vertex
$u_{l-h}$ belongs to the component $K_{v}(1,c^{\prime})$, and so $z_{s}$ does
not belong to this component. We now swap the component
$C_{1,c^{\prime}}=K_{z_{s}}(1,c^{\prime})$, and denote by $\beta^{\prime}$ the
coloring obtained after the swap. Let
${\mathcal{U}}^{\prime}=X^{\beta^{\prime}}_{u}(3)=(uu^{\prime}_{1},\cdots,uu^{\prime}_{l^{\prime}})$.
If the coloring $\beta^{\prime}$ is ${\mathcal{U}}_{>z}$-equivalent to
$\beta$, then for the same reason as in the previous case, $z$ is exactly the
vertex $u^{\prime}_{l^{\prime}-t-1}$, and $X_{z}(c^{\prime})$ is now not
entangled with $\\{v\\}$ since it contains the vertex $z_{s}$ that is missing
the color $1$. This case is similar to the first one. So $\beta^{\prime}$ is
not ${\mathcal{U}}_{>z}$-equivalent to $\beta$, and thus since it is
$\\{u_{l-h}\\}$-equivalent to $\beta$, the component $C_{1,c^{\prime}}$
contains the vertex $u$. We now have to distinguish whether or not, in the
coloring $\beta$ there is an edge $uu_{p}$ colored $1$ in
${\mathcal{U}}_{<z}$.

######  Subcase 59.3.1 (There an edge $uu_{p}$ colored $1$ in
${\mathcal{U}}_{<z}$).

In this case, in the coloring $\beta^{\prime}$, the edge $uu_{p}$ is now
colored $c^{\prime}$, and the edge $uu_{l-h+1}$ is now colored $1$. In the
coloring $\beta^{\prime}$, the fan $X_{u}(4)$ is now a cycle since it contains
the vertex $u_{l-h}$ which is still missing the color $c^{\prime}$, and
$X_{v}(c^{\prime})$ now contains the vertex $z$ which is still missing the
color $4$. The fan $X_{v}(4)$ is still a cycle containing also the vertex $z$,
and the fan ${\mathcal{U}}^{\prime}$ now contains an edge $uu_{l-p}$ colored
$1$ such that $p\leqslant t$.

We now consider the components of $K(1,4)$. If the vertex $z$ does not belong
to the component $K_{v}(1,4)$, then we swap it to obtain a coloring
$\beta^{\prime\prime}$ where $X_{v}(4)$ is now a path. Let
${\mathcal{U}}^{\prime\prime}=X^{\beta^{\prime\prime}}_{u}(3)=(uu^{\prime\prime}_{1},\cdots,uu^{\prime\prime}_{l^{\prime\prime}})$.
If $u\not\in K_{v}(1,4)$, then
$\beta^{\prime\prime}(uu_{l-p})=\beta^{\prime\prime}(uu^{\prime\prime}_{l^{\prime\prime}-t})=1$,
but $p\leqslant t$, and $P(j)$ is true for all $j\leqslant t$, so by Lemma 52
we have a contradiction. Similarly, if $u\in K_{v}(1,4)$, then now
$\beta^{\prime\prime}(uu_{l-t})=1$. Since $\beta^{\prime\prime}$ is
$\bigcup\limits_{j\in[0,t-1]}X_{v}(\beta(uu_{j}))$-equivalent to
$\beta^{\prime}$, by Lemma 51, for any $j\leqslant t$,
$u^{\prime\prime}_{l^{\prime\prime}-j}=u^{\prime}_{l^{\prime}-t}$. So the edge
$uu_{l-t}$ is exactly the edge $uu^{\prime\prime}_{l^{\prime\prime}-t}$. This
edge is colored $1$, and $P(j)$ is true for all $j\leqslant t$, so by Lemma
52, we have a contradiction.

So the vertex $z$ belongs to $K_{v}(1,4)$, and therefore the vertex $z_{s}$
does not belong to this component. We now swap the component
$C_{1,4}=K_{z_{s}}(1,4)$, and denote by $\beta^{\prime\prime}$ the coloring
obtained after the swap. Let
${\mathcal{U}}^{\prime\prime}=X^{\beta^{\prime\prime}}_{u}(3)=(uu^{\prime\prime}_{1},\cdots,uu^{\prime\prime}_{l^{\prime\prime}})$.
Whether or not the vertex $u$ belongs to the component $C_{1,4}$, the fan
$X_{u}(3)$ contains an edge $uu^{\prime\prime}_{l^{\prime\prime}-j}$ colored
$1$ where $j\leqslant t$ (if $u$ belongs to the component,
$\beta^{\prime\prime}(uu^{\prime\prime}{l^{\prime\prime}-t})=1$, and
$\beta^{\prime\prime}(uu^{\prime\prime}_{l^{\prime\prime}-p})=1$). Moreover,
we have that the fan $X_{u}(4)$ is a cycle containing $z$, the fan $X_{v}(4)$
is a cycle containing $z$, the fan $X_{z}(c)$ is a path, and , and the
property $P(j)$ is true for all $j\leqslant t$, so by Lemma 53, we have a
contradiction.

######  Subcase 59.3.2 (There is no edge colored $1$ in ${\mathcal{U}}_{<z}$).

In this case, the coloring $\beta^{\prime}$ is ${\mathcal{U}}_{\leqslant
z}$-equivalent to $\beta$. We now consider the components of $K(1,4)$. If $z$
does not belong to $K_{v}(1,4)$, then we swap the component $K_{z}(1,4)$ and
obtain a coloring where $X_{u}(3)$ still contains the vertex $z$ which is now
missing the color $1$. In the coloring, the cycle ${\mathcal{V}}$ is still a
minimum cycle since $\beta^{\prime}$ is ${\mathcal{V}}$-equivalent to $\beta$,
so by Lemma 24, we have a contradiction.

So the vertex $z$ belongs to $K_{v}(1,4)$, and thus $z_{s}$ does not belong to
this component. We now swap the component $C_{1,4}=K_{z_{s}}(1,4)$, and denote
by $\beta^{\prime\prime}$ the coloring obtained after the swap. The coloring
$\beta^{\prime\prime}$ is ${\mathcal{U}}_{\leqslant z}$-equivalent to
$\beta^{\prime}$, so $z\in X_{u}(3)$. However, now the fan $X_{z}(c)$ is a
path, by Lemma 48, we have a contradiction.

######  Case 59.4 ($m(z_{s})=c^{\prime}=m(u_{l-t-2})$).

In this case, since $c^{\prime}\not\in\beta({\mathcal{V}})$, without loss of
generality, we assume that $c^{\prime}=5$. We now consider the components of
$K(1,5)$. If $u_{l-t-2}$ does not belong to $K_{z}(4,5)$, then we swap the
component $C_{4,5}=K_{u_{l-t-2}}(4,5)$, and denote by $\beta^{\prime}$ the
coloring obtained after the swap. Let
${\mathcal{U}}^{\prime}=X^{\beta^{\prime}}(3)=(uu^{\prime}_{1},\cdots,uu^{\prime}_{l^{\prime}})$.
The coloring $\beta^{\prime}$ is
$({\mathcal{V}}\cup{\mathcal{U}}_{>z})$-equivalent to $\beta$, and for any
$j\leqslant t$, $u^{\prime}_{l^{\prime}-j}=u_{l-j}$, and
$u^{\prime}_{l^{\prime}-j}=u_{l-j-1}$ otherwise. Note that this means that
$l^{\prime}=l-1$, i.e. $|{\mathcal{U}}^{\prime}|=|{\mathcal{U}}|-1$. If the
color $5$ is not in $X^{\beta}_{v}(4)$, then $X_{v}(4)$ is still a cycle
containing $z$, and thus it does not contain $u_{l-t-2}=M(X_{u}(3),4)$, since
the property $P(t)$ is true, we have a contradiction.

So the color $5$ is in $X^{\beta}_{v}(4)$. If $v$ belongs to $C_{4,5}$, then
we are a in case similar to the previous one where $X^{\beta^{\prime}}_{v}(4)$
is a cycle containing $z$, and thus which does not contain
$u_{l-t-2}=M(X_{u}(3),4)$. Since $P(t)$ is true, we have a contradiction. So
$v$ does not belong to $C_{4,5}$, and now, in the coloring $\beta^{\prime}$,
the fan $X_{v}(5)$ is a comet containing the vertices $z$ and $u_{l-t-2}$ that
are both missing the color $4$. We now consider the components of $K(1,4)$.
Since the property $P(t)$ is true, $X_{v}(4)$ is a saturated cycle, to
$u_{l-t-2}$ belongs to $K_{v}(1,4)$, and thus $z$ does not belong to this
component. We now swap the component $K_{z}(1,4)$, and obtain a coloring where
$\\{uz\\}$ is a $({\mathcal{V}},u)$-independent subfan avoiding $v$, and where
$X_{v}(5)$ is a path containing $z$, by Lemma 34 we have a contradiction.

So the vertex $u_{l-t-2}$ belongs to the component $K_{z}(4,5)$, and
therefore, the vertex $x_{s}$ does not belong to this component. We now swap
the component $K_{z_{s}}(4,5)$, to obtain a coloring
$({\mathcal{V}}\cup{\mathcal{U}})$-equivalent to $\beta$, where $X_{z}(c)$ is
now a path, by Lemma 48, we again get a contradiction.

∎

So the fan ${\mathcal{Z}}$ is entangled with ${\mathcal{V}}$ and
${\mathcal{U}}_{\leqslant u_{l-t-2}}$. We now prove that it is not a comet.
Assume that ${\mathcal{Z}}$ is a comet, then there exists $h<r$ such that
$m(z_{h})=m(z_{r})=c$. By Proposition 59,
$c\not\in\beta({\mathcal{V}})\cup\beta({\mathcal{U}}_{\geqslant u_{l-2-t}}$.
Without loss of generality, we assume that $c=5$, and we now consider the
components of $K(1,5)$. The vertices $z_{h}$ and $z_{r}$ are not both part of
$K_{v}(1,5)$.

If $z_{h}$ does not belong to $K_{v}(1,5)$, then we swap $C_{1,5}=K_{v}(1,5)$,
and denote by $\beta^{\prime}$ the coloring obtained after the swap. Let
${\mathcal{U}}^{\prime}=X^{\beta^{\prime}}_{u}(3)=(uu^{\prime}_{1},\cdots,uu^{\prime}_{l^{\prime}})$.
The property $P(j)$ is true for all $j\leqslant t$, so the coloring
$\beta^{\prime}$ is
$(\bigcup\limits_{j\in[0,p]}X_{v}(\beta(uu_{l-j})))$-equivalent to $\beta$
since each of these fans are saturated cycle. Hence by Lemma 51, for any
$j\leqslant(t+1)$, $u^{\prime}_{l^{\prime}-j}=u_{l-j}$. In particular,
$z=u^{\prime}_{l^{\prime}-t-1}$. If the vertex $z$ does not belong to
$C_{1,5}$ or $c\neq 1$, then the coloring $\beta^{\prime}$ is
${\mathcal{Z}}_{<z_{h}}$ equivalent to $\beta$. The fan $X_{z}(c)$ now
contains the vertex $z_{h}$ which is missing the color $1$, by Proposition 59
we have a contradiction. So the vertex $z$ belongs to $C_{1,5}$, and $c=1$.
Thus, in the coloring $\beta^{\prime}$, the edge $zz_{1}$ is now colored $5$,
and the edge $zz_{s+1}$ is now colored $1$. If the vertex $z_{r}$ belongs to
the component $C_{1,5}$, it is now missing the color $1$ in the coloring
$\beta^{\prime}$, and $X_{z}(1)$ is now a fan that contains this vertex. So
the fan $X_{v}(1)$ is not entangled with ${\mathcal{V}}$, a contradiction by
Proposition 59. If the vertex $z_{r}$ does not belong to the component, then
the fan $X_{z}(1)$ now contains the vertex $z_{s}$ which is missing the color
$1$, again, a contradiction by Proposition 59.

So the vertex $z_{h}$ belongs to $K_{v}(1,5)$, and thus the vertex $z_{r}$
does not belong to the component. We now swap the component
$C_{1,5}=K_{z_{s}}(1,5)$ and denote by $\beta^{\prime}$ the coloring obtained
after the swap. Similarly to the previous case, If the vertex $z$ does not
belong to $C_{1,5}$, or if $c\neq 1$, then the coloring $\beta^{\prime}$ is
${\mathcal{Z}}_{<z_{r}}$-equivalent to the coloring $\beta$, and now
$X_{z}(c)$ contains the vertex $z_{r}$ missing the color $1$, by Proposition
59 this is a contradiction. So the vertex $z$ belongs to $C_{1,5}$, and $c=1$.
In this case, the fan $X_{z}(1)$ stills contains the vertex $z_{r}$ which is
missing the color $1$. Again by Proposition 59, this is a contradiction.

Therefore, the fan ${\mathcal{Z}}$ is a cycle entangled with ${\mathcal{V}}$
and ${\mathcal{U}}_{\geqslant u_{l-t-2}}$ and thus $Q(t)$ is true as desired.
∎

We are now ready to prove that $P(i)$ is true for all $i$.

###  4.6 Proof of $P(i)$

###### Proof of Lemma 33.

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 assume that
$P(i)$ not verified. Without loss of generality, we assume that $i$ is
minimum, ans that the vertices $v$, $u$ and $u^{\prime}$ are respectively
missing the colors $1$, $2$ and $3$. By Lemma 40, the property $P(0)$ is true,
so $i>0$. Assume that $\beta(uu_{l-i})\neq 1$ and let
${\mathcal{X}}=X_{v}(\beta(uu_{l-i}))$.

######  Claim 60.

There is no edge in $E({\mathcal{U}}_{>u_{l-i}})$ colored with a color in
$\beta({\mathcal{V}})$

###### Proof.

The proof is similar to the proof of Claim 58 of Lemma 56. ∎

We first prove that $P_{weak}(i)$ is true (i.e. that ${\mathcal{X}}$ is not a
path).

######  Claim 61.

The property $P_{weak}(i)$ is true.

###### Proof.

Assume that $\beta^{\prime}(uu_{l-i})\neq 1$ and that
${\mathcal{X}}=X_{v}(\beta(uu_{l-i}))$ is a path. Then we have that
$\beta(uu_{l-i})\not\in\beta({\mathcal{V}})$. Without loss of generality, we
assume that $\beta(uu_{l-i})=4$. Moreover, we have that $m(u_{l-i})\neq 1$.
Since $P(j)$ is true for all $j<i$, for all $j<i$, if $\beta(uu_{l-j})\neq 1$,
then $X_{u}(\beta(uu_{l-j})$ is a saturated cycle. We now invert
${\mathcal{X}}$ until we reach a coloring where $X_{v}(4)$ is a path of length
$1$; we denote by $z$ the only vertex of this coloring. Up to a relabeling of
the colors, we assume that $v$ is also missing the color $1$ in
$\beta^{\prime}$. The coloring $\beta^{\prime}$ is ${\mathcal{V}}$-equivalent
to the coloring $\beta$, so ${\mathcal{V}}$ is the same minimum cycle in the
coloring $\beta$. So by Lemma 24 the fan
${\mathcal{U}}^{\prime}=X_{u}(m(u^{\prime}))=(uu^{\prime}_{1},\cdots,uu^{\prime}_{l^{\prime}})$
is a cycle entangled with ${\mathcal{V}}$. Moreover, the coloring
$\beta^{\prime}$ is $(\bigcup\limits_{j<i}X_{v}(\beta(uu_{l-j})))$-equivalent
to $\beta$, so by Lemma 51, for any $j\leqslant i$,
$u^{\prime}_{l^{\prime}-j}=u_{l-j}$, the fan
$X_{v}(\beta^{\prime}(uu^{\prime}_{l^{\prime}-j}))$ is a saturated cycle
containing $u^{\prime}_{l^{\prime}-j-1}$. So in particular,
$uu^{\prime}_{l^{\prime}-i}\in E({\mathcal{U}}^{\prime})$, and there is a
vertex missing the color $4$ in ${\mathcal{U}}^{\prime}$. Let $z^{\prime}$ be
this vertex. Note that since $X_{v}(4)$ is a path, for all $j<i$,
$X_{v}(\beta^{\prime}(uu^{\prime}_{l-j}))$ does not contain the vertex
$z^{\prime}$.

We now swap the edge $vz$, and denote by $\beta^{\prime\prime}$ the coloring
obtained after the swap. If the coloring $\beta^{\prime\prime}$ is
${\mathcal{U}}^{\prime}$-equivalent to $\beta^{\prime}$, then it means that
$v\not\in V({\mathcal{U}}^{\prime})$. So in the coloring
$\beta^{\prime\prime}$ the fan $X_{u}(3)={\mathcal{U}}^{\prime}$ contains the
vertex $z^{\prime}$ which is still missing the color $4$. This color is also
the missing color of the vertex $v$. Thus, ${\mathcal{U}}^{\prime}$ is not
entangled with ${\mathcal{V}}$, and by Lemma 24, we have a contradiction.

So the vertex $v$ belongs to $V({\mathcal{U}}^{\prime})$, and in the coloring
$\beta^{\prime}$, the fan $X_{u}(1)$ contains the vertex $z^{\prime}$ which is
missing the color $4$. If there is an edge $uu^{\prime\prime}$ of
$E(V_{u}(1)_{\leqslant z^{\prime}})$ colored with a color of
$\beta^{\prime\prime}$, then $X_{u}(\beta^{\prime\prime}(uu^{\prime\prime}))$
is not entangled with ${\mathcal{V}}$, so by Lemma 24, we have a
contradiction. Therefore, the subfan $X_{u}(1)_{\leqslant z^{\prime}}$ is a
$({\mathcal{V}},u)$-independent subfan avoiding $v$. The coloring
$\beta^{\prime\prime}$ is ${\mathcal{U}}^{\prime}_{\leqslant v}$-equivalent to
the coloring $\beta^{\prime}$, so in the coloring $\beta^{\prime\prime}$, the
fan ${\mathcal{U}}^{\prime\prime}=X_{u}(3)$ is equal to
$(uu^{\prime}_{1},\cdots,uv,uu^{\prime}_{l^{\prime}-i)},\cdots,uu^{\prime}_{l^{\prime}}=uu^{\prime})$.

Since $P(j)$ is true for all $j<i$, for all $j<i$ the fan
$X_{v}(\beta^{\prime\prime}(uu^{\prime}_{l^{\prime}-j}))$ is a saturated cycle
containing $u^{\prime}_{l^{\prime}-j-1}$. In particular, the fan
$X_{v}(\beta^{\prime\prime}(uu^{\prime}_{l^{\prime}-(i-1)})$ is a saturated
cycle containing $u^{\prime}_{l^{\prime}-i}$. Without loss of generality, we
assume that $m(u^{\prime}_{l^{\prime}-i})=5$. The vertex
$u^{\prime}_{l^{\prime}-i}$ belongs to the component $K_{v}(4,5)$, so the
vertex $z^{\prime}$ does not belong to this component. We now swap the
component $C_{4,5}=K_{z^{\prime}}(4,5)$, and denote by $\beta_{3}$ the
coloring obtained after the swap. Note that $\beta_{3}$ is
${\mathcal{V}}$-equivalent to $\beta^{\prime\prime}$, so by Observation 20 the
cycle ${\mathcal{V}}$ is the same minimum cycle in the coloring $\beta_{3}$.
The coloring $\beta_{3}$ is also ${\mathcal{U}}^{\prime\prime}$-equivalent to
$\beta^{\prime\prime}$, so we still have that
$X_{u}(3)=(uu^{\prime}_{1},\cdots,uv,uu^{\prime}_{l^{\prime}-i},\cdots,uu^{\prime}_{l^{\prime}}=uu^{\prime})$.

If the vertex $z$ does not belong to $C_{4,5}$, then we can swap back the edge
$vz$. The fan $X_{u}(3)=X_{u}(1)$ still contains the vertex $z^{\prime}$ which
is missing the color $5$, and
$X_{v}(\beta^{\prime\prime}(uu^{\prime}_{l^{\prime}-i-1}))$ is still a
saturated cycle containing the vertex $u^{\prime}_{l^{\prime}-i}$. Since
$P(i-1)$ is true, we have a contradiction. So the vertex $z$ belongs to
$C_{4,5}$, and in the coloring $\beta_{3}$ the vertex $z$ is missing the color
$5$.

Since the property $P(j)$ is true for all $j<i$, by Lemma 56, the property
$Q(i-1)$ is true, and so the fan $X_{u^{\prime}_{l-i}}(2)$ is a cycle
containing $z^{\prime}$, and therefore there is an edge
$u^{\prime}_{l^{\prime}-i}z$. We denote by $c^{\prime}$ the color of this
edge. We now swap this edge, and denote by $\beta_{4}$ the coloring obtained
after the swap. The coloring $\beta_{4}$ is ${\mathcal{V}}$-equivalent to
$\beta_{3}$, so the fan ${\mathcal{V}}$ is the same minimum cycle in the
coloring $\beta_{4}$ by Observation 20. The coloring $\beta_{4}$ is also
$X_{u}(3)_{<u^{\prime}_{l^{\prime}-i}}$, so the vertex
$u^{\prime}_{l^{\prime}-i}$ is still in $X_{u}(3)$. Note that now the vertex
$u^{\prime}_{l^{\prime}-i}$ and $z^{\prime}$ are both missing the color
$c^{\prime}$. We now have to distinguish the case.

######  Case 61.1 ($c^{\prime}=1$).

In this case, the fan $X_{u}(1)$ contains the vertex $z^{\prime}$ missing the
color $1$, and the fan $X_{u}(3)$ contains the vertex
$u^{\prime}_{l^{\prime}-i}$ missing the color $1$. So the fan $X_{u}(3)$ is a
comet containing two vertices missing the color $1$, so by Lemma 24, we have a
contradiction.

######  Case 61.2 ($c^{\prime}\in\beta_{3}({\mathcal{V}})$).

In this case, since $u^{\prime}_{l^{\prime}-i}\in V(X_{u}(3))$, the fan
$X_{u}(3)$ is not entangled with ${\mathcal{V}}$, so by Lemma 24, we have a
contradiction.

Without loss of generality, we now assume that $c^{\prime}=6$.

######  Case 61.3 ($6\in\beta_{3}(X_{u}(3)_{<u^{\prime}_{l^{\prime}-i}})$).

In this case, the fan $X_{u}(3)$ is now a comet where two vertices are missing
the color $6$, thus by Lemma 24, we also have a contradiction.

######  Case 61.4 ($6\in\beta_{3}(X_{u}(3)_{>u^{\prime}_{l^{\prime}-i}})$).

Let $t<i$ such that $m^{\beta_{3}}(u^{\prime}_{l^{\prime}-t})=6$. Since
$P(t-1)$ is true, in the coloring $\beta_{3}$, the fan $X_{v}(6)$ is a cycle
containing $u^{\prime}_{l^{\prime}-t}$. Since $P(i-1)$ is true, the fan
$X_{v}(5)$ is a cycle containing $u^{\prime}_{l^{\prime}-i}$. We first prove
that in the coloring $\beta_{3}$, we have $X_{v}(5)=X_{v}(6)$. In the coloring
$\beta_{4}$, the vertex $u^{\prime}_{l^{\prime}-i}$ is missing the color $6$,
so the fan $X_{u}(3)$ is equal to
$(uu^{\prime}_{1},\cdots,uv,uu^{\prime}_{l^{\prime}-i},uu^{\prime}_{l^{\prime}-(t-1)},\cdots,uu^{\prime}_{l^{\prime}}=uu^{\prime})$,
and $u^{\prime}_{l^{\prime}-i}$ is now the vertex missing the color $6$ in
this cycle. Since $P(t-1)$ is true, the fan $X_{v}(6)$ is now a cycle
containing $u^{\prime}_{l^{\prime}-i}$. The only vertices whose missing color
is different in $\beta_{3}$ and $\beta_{4}$ are the vertices
$u^{\prime}_{l^{\prime}-i}$ and $z^{\prime}$. In the coloring $\beta_{3}$,
since $z^{\prime}\not\in X_{v}(6)$, if $u^{\prime}_{l^{\prime}-i}\not\in
V(X_{v}(6))$ the coloring $\beta_{4}$ is $X_{v}(6)$-equivalent to the coloring
$\beta_{3}$. This means that in the coloring $\beta_{4}$, the fan $X_{v}(6)$
is a cycle containing the vertex $u^{\prime}_{l^{\prime}-t}$, and not
containing $u^{\prime}_{l^{\prime}-i}$, a contradiction. So in the coloring
$\beta_{3}$, the vertex $u^{\prime}_{l^{\prime}-i}$ belongs to $X_{v}(6)$, and
thus $X_{v}(5)=X_{v}(6)$ as desired.

So, in the coloring $\beta_{3}$, the cycle $X_{v}(5)$ contains the vertex
$u^{\prime}_{l^{\prime}-t}$ which is missing the color $6$. We now consider
the coloring $\beta_{4}$. The fan $X_{v}(5)$ still contains the vertex
$u^{\prime}_{l^{\prime}-t}$ which is still missing the color $6$. The fan
$X_{v}(6)$ is a saturated cycle containing the vertex
$u^{\prime}_{l^{\prime}-i}$, so the fna $X_{v}(5)$ is a comet containing
$X_{v}(6)$ as a subfan. The cycle $X_{v}(6)$ is saturated, so
$u^{\prime}_{l^{\prime}-i}$ belongs to $K_{v}(4,6)$, and thus $z^{\prime}$
does not belong to this component.

We now swap the component $C_{4,6}=K_{z^{\prime}}(4,6)$, and denote by
$\beta_{5}$ the coloring obtained after the swap. The coloring $\beta_{5}$ is
${\mathcal{V}}$-equivalent to $\beta_{4}$, so the fan ${\mathcal{V}}$ is the
same minimum cycle in the coloring $\beta_{5}$. Since the vertex
$u^{\prime}_{l^{\prime}-i}\not\in C_{4,6}$, and
$\beta_{4}(uu^{\prime}_{l^{\prime}-})=4$, the vertex $u$ does not belong
either to $C_{4,6}$, and therefore the coloring $\beta_{5}$ is
$X_{u}(3)$-equivalent to the coloring $\beta_{4}$. The fan $X_{u}(1)$ still
contains the vertex $z^{\prime}$ which is now missing the color $4$, so the
subfan $X_{u}(1)_{\leqslant z^{\prime}}$ is a $({\mathcal{V}},u)$-independent
subfan avoiding $v$. By Lemma 34, the fan $X_{v}(1)$ is a path that does not
contain $z^{\prime}$. In the coloring $\beta_{5}$, the vertex $z$ is still
missing the color $5$, and we still have $\beta_{5}(vz)=1$. If the vertex
$u^{\prime}_{l^{\prime}-t}$ does to belong to $C_{4,6}$, then the coloring
$\beta_{5}$ is $X_{v}(5)$-equivalent to $\beta_{4}$, and therefore the fan
$X_{v}(1)$ is a comet containing $X_{v}(6)$ as a subfan. So the vertex
$u^{\prime}_{l^{\prime}-t}$ belongs to the component $C_{4,6}$, and it is now
missing the color $4$.

In the coloring $\beta_{5}$, the fan $X_{u}(5)$ still contains the vertex
$u^{\prime}_{l^{\prime}-t}$ which is now missing the color $4$. So there is no
edge $uu^{\prime\prime}$ in $E(X_{u}(5)_{\leqslant
u^{\prime}_{l^{\prime}-t}}))$ colroed with a color in
$\beta_{5}({\mathcal{V}})$, otherwise, $X_{u}(\beta_{5}(uu^{\prime\prime}))$
is not entangled with ${\mathcal{V}}$, and by Lemma 24 we have a
contradiction. So the subfan $X_{u}(5)_{\leqslant u^{\prime}_{l^{\prime}-t}}$
is a $({\mathcal{V}},u)$-independent subfan avoiding $v$. By Lemma 34, the fan
$X_{v}(5)$ is a path that does not contain $u^{\prime}_{l^{\prime}-t}$, a
contradiction.

######  Case 61.5
($6\not\in\beta_{3}(X_{u}(3))\cap\beta_{3}({\mathcal{V}})\cup\\{1\\}$).

In the coloring $\beta_{4}$, the vertex $u^{\prime}_{l^{\prime}-i}$ is missing
the color $6$, and $uu^{\prime}_{l^{\prime}-i}\in E(X_{u}(3))$. So we have
$X_{u}(6)=X_{u}(3)$. Since the fan $X_{u}(5)$ also contains the vertex
$u^{\prime}$, either $X_{u}(5)=X_{u}(6)=X_{u}(3)$, or $X_{u}(5)$ is a comet
which contains $X_{u}(3)$ as a subfan.

######  Subcase 61.5.1 ($X_{u}(5)=X_{u}(3)$).

Let $z^{\prime\prime}$ be the vertex of $X_{u}(3)$ missing the color $5$. Note
that we may have $z^{\prime\prime}=z$. Since $P(i-1)$ is true, the fan
$X_{v}(5)$ is now a cycle containing $z^{\prime\prime}$. But
$u^{\prime}_{l^{\prime}-i}$ is the only vertex whose missing color is
different in $\beta_{3}$ and $\beta_{4}$, so in the coloring $\beta_{4}$, the
fan $X_{v}(5)$ still contains the vertex $u^{\prime}_{l^{\prime}-i}$ which is
now missing the color $6$. Therefore, the fan $X_{v}(6)$ is equal to the fan
$X_{v}(5)$ and is a saturated cycle containing $z^{\prime\prime}$ and
$u^{\prime}_{l^{\prime}-i}$. The vertex $z$ is still missing the color $5$, so
the fan $X_{v}(1)$ is now a comet containing $X_{v}(5)$ as a subfan.

Since the fan $X_{v}(6)$ is saturated, the vertex $u^{\prime}_{l^{\prime}-i}$
belongs to the component $K_{v}{4,6}$, and thus the vertex $z^{\prime}$ does
not belong to this component. We now swap the component
$C_{4,6}=K_{z^{\prime}}(4,6)$, and denote by $\beta_{5}$ the coloring obtained
after the swap. The coloring $\beta_{5}$ is ${\mathcal{V}}$-equivalent to
$\beta_{4}$, so the fan ${\mathcal{V}}$ is a minimum cycle in this coloring.
Now the fan $X_{u}(1)$ still contains the vertex $z^{\prime}$ which is now
missing the color $4$, so it is a $({\mathcal{V}},u)$-independent subfan
avoiding $v$ so by Lemma 34, the fan $X_{v}(1)$ is a path. But the coloring
$\beta_{5}$ is also $X_{v}(1)$-equivalent to the coloring $\beta_{4}$, so the
fan $X_{v}(1)$ is a comet. This is a contradiction.

######  Subcase 61.5.2 ($X_{u}(5)$ is a comet containing $X_{u}(3)$).

Let $u^{\prime}_{l^{\prime}-t}$ be the first vertex of $X_{u}(5)$ which is not
in $X_{u}(3)$, and let $z^{\prime\prime}$ be the vertex of $X_{u}(3)$ missing
the color $c_{t}=m(u^{\prime}_{l^{\prime}-t})$. In the coloring $\beta_{3}$,
since $P(t-1)$ is true, the fan $X_{v}(c_{t})$ is a saturated cycle containing
$u^{\prime}_{l^{\prime}-t}$. If the coloring $\beta_{4}$ is
$X_{v}(c_{t})$-equivalent to the coloring $\beta_{3}$, then in the coloring
$\beta_{4}$ the fan $X_{v}(c_{t})$ still contains the vertex
$u^{\prime}_{l^{\prime}-t}$, and thus does not contain the vertex
$z^{\prime\prime}$. Since $P(t-1)$ is true, we have a contradiction.

So the coloring $\beta_{4}$ is not $X_{v}(c_{t})$-equivalent to the coloring
$\beta_{3}$. Since $u^{\prime}_{l^{\prime}-i}$ and $z^{\prime}$ are the only
vertices whose missing color are different in $\beta_{3}$ and $\beta_{4}$, and
$z^{\prime}\not\in V(X_{v}(c_{t}))$, we have that
$u^{\prime}_{l^{\prime}-i}\in V(X_{v}(c_{t}))$. In the coloring $\beta_{3}$
the vertex $u^{\prime}_{l^{\prime}-i}$ is also in $X_{v}(5)$, so in this
coloring we have $X_{v}(5)=X_{v}(c_{t})$. Therefore, the vertex
$u^{\prime}_{l^{\prime}-t}$ also belongs to $X_{v}(5)$ in the coloring
$\beta_{4}$.

In the coloring $\beta_{4}$, the vertex $u^{\prime}_{l^{\prime}-i}$ is now
missing the color $6$, and since $P(t-1)$ is true, the fan $X_{v}(c_{t})$ is a
saturated cycle containing the vertex $z^{\prime\prime}$. So in this coloring,
we have $X_{v}(c_{t})=X_{v}(6)$. However, in this coloring, the vertex
$u^{\prime}_{l^{\prime}-t}$ still belongs to $X_{v}(5)$, it also belongs to
$X_{u}(5)$ and is still missing hte color $c_{t}$. The cycle $X_{v}(c_{t})$ is
saturated, so the vertex $z^{\prime\prime}$ belongs to the component
$K_{v}(4,c_{t})$, and thus the vertex $u^{\prime}_{l^{\prime}-t}$ does not
belong to this component. We now swap the component
$K_{u^{\prime}_{l^{\prime}-t}}(4,c_{t})$ and denote by $\beta_{5}$ the
coloring obtained after the swap.

The coloring $\beta_{5}$ is ${\mathcal{V}}$-equivalent to $\beta_{4}$, so by
Observation 20, the fan ${\mathcal{V}}$ is a minimum cycle in the coloring
$\beta_{5}$. The coloring $\beta_{5}$ is also $((X_{u}(5)\cup
X_{v}(5))\setminus\\{u^{\prime}_{l^{\prime}-t}\\})$-equivalent to the coloring
$\beta_{4}$, so the vertex $u^{\prime}_{l^{\prime}-t}$ still belongs to both
$X_{u}(5)$ and $X_{v}(5)$. So the subfan $X_{u}(5)_{\leqslant
u^{\prime}_{l^{\prime}-t}}$ is a $({\mathcal{V}},u)$-independent subfan
avoiding $v$, by Lemma 34, the fan $X_{v}(5)$ is a path that does not contain
$u^{\prime}_{l^{\prime}-t}$. Again we have a contradiction.

∎

By the previous claim, we have that ${\mathcal{X}}$ is not a path, we now
prove that it is not a comet. Assume that
${\mathcal{X}}=(vx_{1},\cdots,vx_{t})$ is a comet where $x_{s}$ and $x_{t}$
are missing the same color $c_{s}$. Since $x_{s}$ and $x_{t}$ are both missing
the color $c_{s}$ at least one of them is not in $K_{v}(1,c_{s})$. Since
$P(j)$ is true for all $j<i$, for all $j<i$, if $\beta(uu_{l-j})\neq 1$, then
$X_{v}(\beta(uu_{l-j}))$ is a cycle, so
$\beta({\mathcal{X}})\cap(\bigcup\limits_{j\in[0,i-1]}\beta(X_{v}(\beta(uu_{l-j}))))=\emptyset$.

######  Case 61.6 ($c_{s}\not\in\beta({\mathcal{U}}_{u>_{l-1}})$).

If $x_{s}$ is not in $K_{v}(1,c_{s})$, then we swap the component
$C_{1,c_{s}}=K_{x_{s}}(1,c_{s})$ and obtain a coloring $\beta^{\prime}$ which
is ${\mathcal{V}}$-equivalent to $\beta$, so the fan ${\mathcal{V}}$ is the
same minimum cycle in the coloring $\beta^{\prime}$. In the coloring
$\beta^{\prime}$, the fan $X_{v}(4)$ is now a path. Moreover,
$c_{s}\not\in\beta({\mathcal{U}}_{\geqslant u_{l-i}})$, and by Claim 60, so
$1\not\in\beta({\mathcal{U}}_{\geqslant u_{l-i}})$. Therefore, the coloring
$\beta^{\prime}$ is ${\mathcal{U}}_{\geqslant u_{l-i}}$-equivalent to the
coloring $\beta$. Let
${\mathcal{U}}^{\prime}=X^{\beta^{\prime}}_{u}(3)=(uu^{\prime}_{1},\cdots,uu^{\prime}_{l^{\prime}})$.
Since
$\beta({\mathcal{X}})\cap(\bigcup\limits_{j\in[0,i-1]}\beta(X_{v}(\beta(uu_{l-j}))))=\emptyset$,
the coloring $\beta^{\prime}$ is
$(\bigcup\limits_{j\in[0,i-1]}\beta(X_{v}(\beta(uu_{l-j})))$-equivalent to
$\beta$. So by Lemma 51, for all $j\leqslant i$, we have
$u^{\prime}_{l^{\prime}-i}=u_{l-i}$. In particular
$u^{\prime}_{l^{\prime}-i}=u_{l-i}$. Since
$\beta^{\prime}(uu^{\prime}_{l^{\prime}-i})=4$, and $P{weak}(i)$ is true, the
fan $X_{v}(4)$ is not a path.

Similarly, if $x_{t}\not\in K_{v}(1,c_{s})$, we swap the component
$C_{1,c_{s}}=K_{x_{t}}(1,c_{s})$. Note that ${\mathcal{V}}$ is a minimum
cycle, so it is saturated by Lemma 15, and thus $x_{t}\not\in
V({\mathcal{V}})$. The coloring $\beta^{\prime}$ is therefore
${\mathcal{V}}$-equivalent to ${\mathcal{V}}$, so the fan ${\mathcal{V}}$ is
the same minimum cycle in this coloring. The fan $X_{v}(4)$ is now a path the
coloring $\beta^{\prime}$. Let
${\mathcal{U}}^{\prime}=X^{\beta^{\prime}}_{u}(3)=(uu^{\prime}_{1},\cdots,uu^{\prime}_{l^{\prime}})$.
Similarly to the previous case, the coloring $\beta^{\prime}$ is
${\mathcal{U}}_{>u_{l-i}}$-equivalent to $\beta$ and
$(\bigcup\limits_{j\in[0,i-1]}\beta(X_{v}(\beta(uu_{l-j})))$-equivalent to
$\beta$. So by Lemma 51, for all $j\leqslant i$, we have
$u^{\prime}_{l^{\prime}-j}=u_{l-j}$. In particular,
$u^{\prime}_{l^{\prime}-i}=u_{l-i}$, and
$\beta^{\prime}(uu^{\prime}_{l^{\prime}-i})=4$. Since $P_{weak}(i)$ is true,
the fan $X_{v}(4)$ is not a path, a contradiction.

######  Case 61.7 ($c_{s}\in\beta({\mathcal{U}}_{>u_{l-1}})$).

Let $t^{\prime}$ be such that $m(u_{l-t^{\prime}})=c_{s}$. Since $P(j)$ is
true for all $j<i$, the fan $X_{v}(c_{s})$ is saturated cycle containing
$u_{l-t^{\prime}}=x_{t}$. So the vertex $x_{s}$ does not belong to
$K_{v}(1,c_{s})$. We now swap the component $C_{1,c_{s}}=K_{x_{s}}(1,c_{s})$
to obtain a coloring $\beta^{\prime}$ where $X_{v}(4)$ is now a path. The
coloring $\beta^{\prime}$ is ${\mathcal{V}}$-equivalent to $\beta$, so by
Observation 20, the cycle ${\mathcal{V}}$ is the dame minimum cycle in the
coloring $\beta^{\prime}$. If the vertex $u$ does not belong to $C_{1,c_{s}}$,
then the coloring $\beta^{\prime}$ is also ${\mathcal{U}}$-equivalent to
$\beta$, and thus $X_{u}(3)={\mathcal{U}}$. Since
$\beta^{\prime}(uu_{l-i})=4$, and $P_{weak}(i)$ is true, the fan $X_{v}(4)$ is
not a path. this is a contradiction.

So the vertex $u$ belongs to $C_{1,c_{s}}$, and in the coloring
$\beta^{\prime}$, the edge $uu_{l-(t^{\prime}-1)}$ is now colored $1$. Let
${\mathcal{U}}^{\prime}=X^{\beta^{\prime}}_{u}(3)$. The coloring
$\beta^{\prime}$ is ${\mathcal{U}}_{>u_{l-t^{\prime}}}$-equivalent to $\beta$.
The coloring $\beta^{\prime}$ is also
$(\bigcup\limits_{j\in[0,t^{\prime}-1]}\beta(X_{v}(\beta(uu_{l-j})))$-equivalent
to $\beta$, so by Lemma 51, for any $j\leqslant t^{\prime}$ we have
$u^{\prime}_{l^{\prime}-j}=u_{l-j}$. In particular,
$u^{\prime}_{l^{\prime}-(t^{\prime}-1)}=u_{l-(t^{\prime}-1)}$. Now the edge
$uu^{\prime}_{l^{\prime}-(t^{\prime}-1)}$ is colored $1$, and the fan
$X_{v}(4)$ is a path. Since $P(j)$ is true for all $j\leqslant t^{\prime}$, by
Lemma 52 there is not path around $v$, a contradiction.

So the fan ${\mathcal{X}}=(vx_{1},\cdots,vx_{t})$ is a cycle, we now prove
that it is saturated. Otherwise, there exists $x_{s}$ such that $x_{s}\not\in
K_{v}(1,m(x_{s}))$. Note that since $P(j)$ is true for all $j<i$, for all
$j<i$, the fan $X_{v}(\beta(uu_{l-j}))$ is a saturated cycle, so
$\beta(X_{v}(\beta(uu_{l-j})))\cap\beta({\mathcal{X}})=\emptyset$, and in
particular $x_{s}\not\in\beta({\mathcal{U}}_{>u_{l-i}})$.

######  Case 61.8 ($m(x_{s})\neq 4$).

Without loss of generality, assume that $m(x_{s})=5$. Since $x_{s}$ does not
belong to $K_{v}(1,5)$, we swap the component $C_{1,5}=K_{x_{s}}(1,5)$ and
obtain a coloring $\beta^{\prime}$ where $X_{v}(4)$ is a path. 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}$. Let
${\mathcal{U}}^{\prime}=X_{u}^{\beta^{\prime}}(3)=(uu^{\prime}_{1},\cdots,uu^{\prime}_{l^{\prime}})$.
Moreover, $5\not\in\beta({\mathcal{U}}_{\geqslant u_{l-i}})$, and by Claim 60,
the color $1$ does not appear either in ${\mathcal{U}}_{>u_{l-i}}$. The
coloring $\beta^{\prime}$ is also
$(\bigcup\limits_{j\in[0,i-1]}\beta(X_{v}(\beta(uu_{l-j})))$-equivalent to
$\beta$, so by Lemma 51, for any $j\leqslant i$, we have
$u^{\prime}_{l^{\prime}-j}=u_{l-j}$. In particular,
$u^{\prime}_{l^{\prime}-i}=u_{l-i}$. The edge $uu^{\prime}_{l^{\prime}-i}$ is
still colored $4$ in the coloring $\beta^{\prime}$ and the property
$P_{weak}(i)$ is true, so $X_{v}(4)$ is not a path, a contradiction.

######  Case 61.9 ($m(x_{s})=4$).

In this case, we swap the component $C_{1,4}=K_{x_{s}}(1,4)$ and denote by
$\beta^{\prime}$ the coloring obtained after the swap. If the vertex $u$ does
not belong to this component, then we are in a coloring similar to the
previous case. So the vertex $u$ belongs to $C_{1,4}$, and we have
$\beta^{\prime}(uu_{l-i})=1$. In the coloring $\beta^{\prime}$ is
${\mathcal{V}}$-equivalent to $\beta$, so by Observation 20, the cycle
${\mathcal{V}}$ is the same minimum cycle in this coloring. The fan $X_{v}(4)$
is now a path in the coloring $\beta^{\prime}$. Let
${\mathcal{U}}^{\prime}=X^{\beta^{\prime}}_{u}(3)=(uu^{\prime}_{1},\cdots,uu^{\prime}_{l^{\prime}})$.
The coloring $\beta^{\prime}$ is ${\mathcal{U}}_{>u_{l-i}}$-equivalent to
$\beta$, and is also
$(\bigcup\limits_{j\in[0,i-1]}\beta(X_{v}(\beta(uu_{l-j})))$-equivalent to
$\beta$. So by Lemma 51 for all $j\leqslant i$, we have
$u^{\prime}_{l^{\prime}-j}=u_{l-j}$. In particular
$u^{\prime}_{l^{\prime}-i}=u_{l-i}$. The property $P(j)$ is true for all
$j<i$,a nd $P_{weak}(i)$ is also true, so by Lemma 52 there is no path around
$v$. This is a contradiction.

So the fan ${\mathcal{X}}=(vx_{1},\cdots,vx_{t})$ is a saturated cycle, and
thus $x_{t}\in K_{v}(1,4)$. Since $P(i)$ is false, we have $x_{t}\neq
u_{l-i-1}$. So the vertex $u_{l-i-1}$ which is also missing the color $4$ does
not belong to $K_{v}(1,4)$. We now swap the component
$C_{1,4}=K_{u_{l-i-1}}(1,4)$ and denote by $\beta^{\prime}$ the coloring
obtained after the swap. Be Lemma 50, the vertex $u$ belongs to $C_{1,4}$,
there is an edge $uu^{\prime\prime}$ colored $1$ in
${\mathcal{U}}_{<u_{l-i}}$, and the subfan $X_{u}(1)_{\leqslant u_{l-i}}$ is a
$({\mathcal{V}},u)$-independent subfan. So in the coloring $\beta^{\prime}$,
the vertex $u_{l-i}$ is now missing the color $1$, the edge
$uu^{\prime\prime}$ is now colored $4$, and the subfan $X_{u}(4)_{\leqslant
u_{l-i}}$ is a $({\mathcal{V}},u)$-independent subfan avoiding $v$. By Lemma
34, the fan $X_{v}(4)$ is a path. However, the coloring $\beta^{\prime}$ is
$X_{v}(4)$-equivalent to the coloring $\beta$, so the fan $X_{v}(4)$ is a
cycle, a contradiction. ∎

##  5 Cycles interactions

In this section we prove Lemma 23.

###### Proof.

We first prove that all the three cycles are tight and saturated.

######  Claim 62.

The cycles ${\mathcal{V}}$, ${\mathcal{X}}$, and ${\mathcal{Y}}$ are saturated
and tight.

###### Proof.

As the fan ${\mathcal{V}}$ is not invertible, it is saturated by Lemma 15. If
${\mathcal{X}}$ or ${\mathcal{Y}}$ are not saturated (without loss of
generality, we can assume that ${\mathcal{X}}$ is not saturated), then we swap
a component $K_{u}(c_{v},c_{u})$ with $u$ in ${\mathcal{X}}$ and $u\not\in
K_{v}(c_{v},c_{u})$ to transform $\beta$ into a coloring where ${\mathcal{V}}$
is still a cycle of the same size, and where a fan around $v$ is a path, by
Lemma 22, ${\mathcal{V}}$ is invertible in this coloring, and so it is in the
original coloring. Similarly, assume that ${\mathcal{X}}$ or ${\mathcal{Y}}$
is not tight, without loss of generality, we can assume that ${\mathcal{X}}$
is not tight. Then we can find two consecutive vertices of ${\mathcal{X}}$,
$u_{i}$, and $u_{i-1}$ such that the component
$K_{u_{i-1}}(m(u_{i}),m(u_{i-1}))$ does not contain $u_{i}$. If we swap this
component, we obtain a coloring where ${\mathcal{V}}$ is still a cycle of the
same size, and where a fan around $v$ is a comet, again by Lemma 22,
${\mathcal{V}}$ is invertible in this coloring, and so it is in the coloring
$\beta$. ∎

By Lemma 24, we already have that if $(z,z^{\prime})\in{\mathcal{V}}^{2}$,
then $X_{z}(c_{z^{\prime}})$ is a cycle containing $z^{\prime}$, so we now
assume that $(z,z^{\prime})$ is not in ${\mathcal{V}}^{2}$.

######  Claim 63.

The fan ${\mathcal{Z}}$ is not a path.

###### Proof.

As ${\mathcal{Z}}$ is a path, we invert it until we reach a coloring where
$m(z)\in(\beta({\mathcal{V}})\cup\beta({\mathcal{X}})\cup\beta({\mathcal{Y}}))\setminus\\{m_{\beta}(z)\\}$.
In this coloring, the fan ${\mathcal{V}}$ is still a cycle of the same size,
and, there is a fan around $v$ which is a path or a comet, by Lemma 22, this
is a contradiction. ∎

######  Claim 64.

The fan ${\mathcal{Z}}$ is entangled with ${\mathcal{V}}$, ${\mathcal{X}}$,
and ${\mathcal{Y}}$.

###### Proof.

Let us assume that there exists
$z^{\prime\prime}\in{\mathcal{Z}}\setminus({\mathcal{V}}\cup{\mathcal{Y}}\cup{\mathcal{X}})$
with
$m(z^{\prime\prime})\in(\beta({\mathcal{V}})\cup\beta({\mathcal{Y}})\cup\beta({\mathcal{X}}))\setminus\\{c_{z}\\}$.
If $m(z^{\prime\prime})=c_{v}$, since the cycles are saturated by Claim 62,
$K_{z^{\prime\prime}}(c_{z},c_{v})$ does not contain any vertex of
$({\mathcal{V}}\cup{\mathcal{Y}}\cup{\mathcal{X}})$, and after swapping it, we
obtain a coloring where ${\mathcal{V}}$ is still a cycle of the same size and
where ${\mathcal{Z}}$ is a path, by Claim 63, this is a contradiction. If
$m(z^{\prime\prime})\neq c_{v}$, then, since the cycles are saturated, the
component $K_{z^{\prime\prime}}(c_{v},m(z^{\prime\prime}))$ does not contain
any vertex of $({\mathcal{V}}\cup{\mathcal{Y}}\cup{\mathcal{X}})$, so if we
swap it, we obtain a coloring which corresponds to the previous case. ∎

######  Claim 65.

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

###### Proof.

Assume that ${\mathcal{Z}}$ is a comet, there exist $z_{1}$ and $z_{2}$ with
$m(z_{1})=m(z_{2})=c$. By the previous claim, we have that
$c\not\in(\beta({\mathcal{V}})\cup\beta({\mathcal{X}})\cup\beta({\mathcal{Y}}))$,
otherwise, ${\mathcal{Z}}$ is not entangled with one of these cycles. Hence,
the component $K_{z}(c,m(z))$ either contains $z_{1}$ or $z_{2}$, and without
loss of generality we can assume that $z_{1}\not\in K_{z}(c,m(z))$. If we swap
$K_{z_{1}}(c,m(z))$ we obtain a coloring where no edge of
$({\mathcal{V}}\cup{\mathcal{X}}\cup{\mathcal{Y}})$ has changed and where
${\mathcal{Z}}$ is a path, by Claim 63 this is a contradiction. ∎

By the previous claims, ${\mathcal{Z}}$ is a cycle, and as it is entangled
with the three other cycles, it contains $z^{\prime}$; this concludes the
proof.

∎

#### Acknowledgements.

We thank Marthe Bonamy, František Kardoš and Éric Sopena for helpful
discussions, and gratefully thank Penny Haxell for pointing out a mistake in
an earlier version

## References

  * [AC16] Armen S. Asratian and Carl Johan Casselgren.  Solution of Vizing’s problem on interchanges for the case of graphs with maximum degree 4 and related results.  Journal of Graph Theory, 82(4):350–373, 2016.
  * [BDK+21] Marthe Bonamy, Oscar Defrain, Tereza Klimošová, Aurélie Lagoutte, and Jonathan Narboni.  On vizing’s edge colouring question.  arXiv preprint arXiv:2107.07900, 2021.
  * [MMS12] Jessica McDonald, Bojan Mohar, and Diego Scheide.  Kempe equivalence of edge-colorings in subcubic and subquartic graphs.  Journal of Graph theory, 70(2):226–239, 2012.
  * [Moh06] Bojan Mohar.  Kempe equivalence of colorings.  In Graph Theory in Paris, pages 287–297. Springer, 2006.