[proofplan] The lower bound $\chi'(G) \geq \Delta(G)$ is immediate: edges meeting at a vertex of degree $\Delta(G)$ must all receive distinct colours. The content of the theorem is the upper bound $\chi'(G) \leq \Delta(G) + 1$, which we prove by induction on $|E(G)|$. In the inductive step, we remove an edge $xv$, colour the remainder with $\Delta(G) + 1$ colours by hypothesis, and extend the colouring to $xv$ using Vizing's fan construction. The fan builds a sequence $v = v_1, v_2, \ldots, v_k$ of neighbours of $x$ and missing colours $c_1, c_2, \ldots, c_k$, each $c_i$ missing at $v_i$ and equal to the colour of $xv_{i+1}$. The sequence must terminate (by finiteness of $N(x)$), yielding either a missing colour at $x$ (immediate recolouring) or a repeated colour in the sequence. The repeat case is resolved by swapping colours on a two-coloured Kempe chain; a cardinality argument on Kempe-chain endpoints forces a contradiction, completing the extension. [/proofplan] [step:Establish the lower bound $\chi'(G) \geq \Delta(G)$ by counting at a max-degree vertex] Let $x \in V(G)$ satisfy $\deg(x) = \Delta(G)$. The $\Delta(G)$ edges incident to $x$ pairwise share the endpoint $x$, so any proper edge colouring must assign them pairwise distinct colours. Hence at least $\Delta(G)$ colours are required, giving $\chi'(G) \geq \Delta(G)$. [/step] [step:Set up induction on $|E(G)|$ for the upper bound $\chi'(G) \leq \Delta(G) + 1$] We induct on the number of edges. The statement to be proved is: every graph $G$ admits a proper edge colouring with at most $\Delta(G) + 1$ colours. **Base case: $E(G) = \varnothing$.** Then $\Delta(G) = 0$ and the empty edge colouring (vacuously) uses $0 \leq \Delta(G) + 1 = 1$ colours. **Inductive step.** Fix $G$ with $|E(G)| \geq 1$ and assume the statement for every graph with strictly fewer edges. Pick any edge $xv \in E(G)$ and consider $G - xv$. Since $\Delta(G - xv) \leq \Delta(G)$, the inductive hypothesis gives a proper edge colouring of $G - xv$ using at most $\Delta(G - xv) + 1 \leq \Delta(G) + 1$ colours. We use the full palette of $k := \Delta(G) + 1$ colours $\{c_0, \ldots, c_{\Delta(G)}\}$. Our task is to extend this colouring of $G - xv$ to a proper colouring of $G$ by assigning a colour to the edge $xv$. [guided] The inductive hypothesis gives us a colouring of $G - xv$ that uses at most $\Delta(G) + 1$ colours. We are free to use this full palette, and we often need to — the extension to $xv$ may not be possible with fewer. The key structural fact we exploit throughout the extension is this **missing-colour principle**: for any vertex $w$ with $\deg_G(w) \leq \Delta(G)$, the edges incident to $w$ use at most $\Delta(G)$ distinct colours in our palette of $\Delta(G) + 1$, so at least one colour is **missing** at $w$. This holds at every vertex of $G$, and in particular at $x$ and at every neighbour of $x$. The naive attempt — "just pick a colour missing at both $x$ and $v$" — may fail: the colour missing at $x$ might already be used on some edge $vv'$, and vice versa. Vizing's fan resolves this by chasing a sequence of such conflicts until they are forced to resolve. [/guided] [/step] [step:Build the Vizing fan sequence of neighbours and missing colours at $x$] By the missing-colour principle, there exists a colour $c_0$ missing at $x$ (none of the edges $xu$ for $u \in N(G)(x)$ in $G - xv$ uses $c_0$). We now construct a sequence $v_1, v_2, v_3, \ldots$ of neighbours of $x$ in $G$ and a sequence $c_1, c_2, c_3, \ldots$ of colours inductively: - Set $v_1 := v$, and let $c_1$ be any colour missing at $v_1$. - Given $v_i$ and $c_i$ (where $c_i$ is missing at $v_i$): if no edge $x u$ ($u \in N(x)$ in $G - xv$) has colour $c_i$, or if $c_i$ equals a previously chosen $c_j$ with $j < i$, or if $c_i$ is missing at $x$, we stop. Otherwise there is a unique $v_{i+1} \in N(x)$ with the edge $x v_{i+1}$ coloured $c_i$ (uniqueness follows from properness of the colouring at $x$). Pick any colour $c_{i+1}$ missing at $v_{i+1}$. **Termination.** The sequence $v_1, v_2, \ldots$ consists of distinct neighbours of $x$ as long as the construction continues without a colour repetition in $c_1, c_2, \ldots$: if $v_i = v_j$ with $i < j$, then $c_{i-1}$ and $c_{j-1}$ both equal the colour of edge $xv_i$, forcing $c_{i-1} = c_{j-1}$, which would have already triggered termination. Since $N(x)$ is finite, the sequence terminates in one of the two cases: - **Case (a):** We reach $c_k$ with $c_k$ missing at $x$. - **Case (b):** We reach $c_k$ with $c_k = c_i$ for some $i < k$, and $c_k$ is not missing at $x$ (otherwise we would have stopped in Case (a) first). [guided] The construction is a **fan**: starting from $v_1 = v$, each $v_{i+1}$ is the unique neighbour of $x$ whose incident edge at $x$ carries the colour $c_i$ (which was missing at $v_i$). The picture is a rotating sequence of "conflict resolutions" — each time we declare what colour we want to put on $xv_i$, we are blocked by the existing colour of some other edge at $x$, which points us to the next neighbour. **Why must the sequence terminate?** There are three ways to stop: 1. $c_i$ is missing at $x$ (Case (a)). 2. $c_i$ has appeared before in the sequence (Case (b)). 3. No edge at $x$ carries colour $c_i$ (which is just Case (a) restated: $c_i$ missing at $x$ means no edge at $x$ carries it). Since each $c_i$ is one of $\Delta(G) + 1$ colours and the $v_i$ are distinct (as argued above), after at most $\Delta(G) + 1$ steps we must either hit a repeat in $\{c_i\}$ (Case (b)) or run out of neighbours of $x$ (forcing the "no edge at $x$ carries $c_i$" termination, which is Case (a)). Finiteness of $N(x)$ and the palette forces termination. **Uniqueness of $v_{i+1}$.** The existing colouring of $G - xv$ is proper, so at $x$ each colour appears on at most one incident edge. If $c_i$ is not missing at $x$, exactly one edge $xu$ carries it; we set $v_{i+1} := u$. This is well-defined. [/guided] [illustration:vizing-fan] [/step] [step:Resolve Case (a) by shifting colours back along the fan to free the edge $xv$] Suppose the sequence terminates in Case (a): $c_k$ is missing at $x$, for some $k \geq 1$. **Shift procedure.** Recolour edge $xv_k$ with colour $c_k$. This is proper: $c_k$ is missing at $x$ by assumption, and $c_k$ is missing at $v_k$ by construction. Now colour $c_{k-1}$ is no longer used on any edge at $x$ (the edge $xv_k$ that previously carried $c_{k-1}$ has been relabelled $c_k$), so $c_{k-1}$ is missing at $x$. Recolour $xv_{k-1}$ with $c_{k-1}$: properness at $x$ holds (just argued), and at $v_{k-1}$ by construction ($c_{k-1}$ missing at $v_{k-1}$). Iterating this shift from index $k$ down to index $1$, we ultimately colour $xv_1 = xv$ with $c_1$. All edge colours in $G$ are now validly assigned. [guided] The shift procedure is a cascade: each step frees up the previous colour at $x$ so that the next-smaller-index edge can be recoloured with it. Concretely, the sequence of recolourings is: - $xv_k$ gets colour $c_k$. (Previously $c_{k-1}$; now $c_{k-1}$ is free at $x$.) - $xv_{k-1}$ gets colour $c_{k-1}$. (Previously $c_{k-2}$; now $c_{k-2}$ is free at $x$.) - $\vdots$ - $xv_1$ gets colour $c_1$. (Previously uncoloured — this is the edge $xv$ we needed to extend.) **Why does each step preserve properness?** For the recolouring of $xv_i$ to $c_i$: - At $x$: $c_i$ has just been freed (the edge previously carrying $c_i$, namely $xv_{i+1}$, was relabelled in the previous shift step). - At $v_i$: $c_i$ is missing at $v_i$ by construction of the fan. So at every step the recolouring is a proper edge colouring, and the cascade produces a proper colouring of all of $G$, extending the original colouring of $G - xv$ to include $xv$. Case (a) is resolved. [/guided] [/step] [step:Reduce Case (b) to a canonical form where the first repetition is $c_k = c_1$] Suppose the sequence terminates in Case (b): $c_k = c_i$ for some $1 \leq i < k$, and $c_k$ is not missing at $x$. We first argue that we may assume, without loss of generality, $i = 1$ — that is, the first repeated colour is $c_1$. Note that if $i > 1$, the shift procedure from Case (a) can be applied along the prefix $v_1, v_2, \ldots, v_{i-1}, v_i$: since $c_i$ is the colour of the edge $xv_{i+1}$ and also the missing colour at $v_i$, we may recolour $xv_i$ with $c_i$, which frees $c_{i-1}$ at $x$, and so on back to $xv_1$. But this would colour $xv_1 = xv$ with $c_1$ and complete the colouring — so if we had stopped at $i > 1$ with this structure, we would be done already, not in Case (b). The remaining genuine Case (b) scenario is thus $i = 1$: $c_k = c_1$ and $c_1$ is not missing at $x$. In this canonical form, $c_1$ is simultaneously: - missing at $v_1$ (by construction), - missing at $v_k$ (by construction, as $c_k$ is missing at $v_k$ and $c_k = c_1$). [guided] This reduction is the standard trick for Vizing: **without loss of generality, the first colour repetition is at index $1$**. The argument is that any earlier partial resolution would have already colourеd $xv$ via the Case (a) shift procedure, so if we are still in Case (b) we must have $c_k = c_1$. The resulting canonical scenario is: $c_1$ is missing at both $v_1$ and $v_k$, and $c_1$ is used on exactly one edge at $x$ (namely $xv_2$). We also retained $c_0$: still missing at $x$. The next step uses these two colours $c_0$ and $c_1$ to build a Kempe chain and derive a contradiction with connectedness. [/guided] [/step] [step:Analyse the $\{c_0, c_1\}$-components through Kempe chain swaps] Consider the subgraph $H$ of $G$ consisting of all edges coloured $c_0$ or $c_1$. Every vertex of $H$ has degree at most $2$ (at most one edge of each of the two colours by properness), so every connected component of $H$ is either a simple path or an even cycle. (A cycle must alternate the two colours, hence has even length.) Key facts about endpoints: a vertex $w$ in $H$ has $H$-degree $1$ (i.e., is a path endpoint) if and only if exactly one of $c_0, c_1$ is missing at $w$. - **At $x$:** $c_0$ is missing and $c_1$ is present (used on $xv_2$). So $x$ has $H$-degree $1$: it is a path endpoint. - **At $v_1$:** $c_1$ is missing. The colour $c_0$ at $v_1$ may or may not be used. If $c_0$ is also missing at $v_1$, then $v_1$ has $H$-degree $0$ — it is an isolated vertex in $H$, hence both endpoints of the degenerate path at $v_1$. If $c_0$ is used at $v_1$ (by exactly one edge, by properness), then $v_1$ has $H$-degree $1$: path endpoint. - **At $v_k$:** $c_1$ is missing. Same analysis: $v_k$ is a path endpoint of $H$ (or isolated). **Kempe swap.** For any component $C$ of $H$, swapping the two colours $c_0 \leftrightarrow c_1$ on the edges of $C$ produces another proper edge colouring of $G - xv$. (Inside $C$ properness is preserved by the swap; outside $C$ no edge uses $c_0$ or $c_1$ adjacent to $C$ in a way that could conflict, by definition of $C$ as a maximal $\{c_0, c_1\}$-component.) **Sub-case: $v_1$ and $x$ in different $H$-components.** Let $C_{v_1}$ be the component of $H$ containing $v_1$. Swap $c_0 \leftrightarrow c_1$ on $C_{v_1}$. After the swap, $c_0$ is now missing at $v_1$ (previously $c_1$ was missing; the swap on $v_1$'s component flips this), and $c_0$ remains missing at $x$ (since $x \notin C_{v_1}$, the swap does not affect edges incident to $x$). The colours on $xv_2, \ldots, xv_k$ are unchanged (none of these edges is in $C_{v_1}$ — they are incident to $x$, not $v_1$). So $c_0$ is missing at both $x$ and $v_1$: colour $xv_1 = xv$ with $c_0$, completing the proper colouring. Done. **Sub-case: $v_k$ and $x$ in different $H$-components.** Symmetrically, let $C_{v_k}$ be the component of $H$ containing $v_k$. Swap $c_0 \leftrightarrow c_1$ on $C_{v_k}$. After the swap, $c_0$ is missing at $v_k$ and remains missing at $x$. Now the shift procedure of Case (a) can be run: recolour $xv_k$ with $c_0$ (valid: $c_0$ missing at both $x$ and $v_k$), which frees $c_{k-1}$ at $x$; recolour $xv_{k-1}$ with $c_{k-1}$; continue down to $xv_1$ getting $c_1$. (Note: even after the swap, the colours $c_1, c_2, \ldots, c_{k-1}$ on edges $xv_2, \ldots, xv_k$ are unchanged because these edges are incident to $x$, and $x \notin C_{v_k}$ means the swap is disjoint from them.) Done. **Remaining sub-case: $x$, $v_1$, and $v_k$ all in the same $H$-component $C$.** Since $C$ is a path or even cycle and a path has at most two endpoints, $C$ being a cycle would mean no endpoints, but $x$, $v_1$, $v_k$ all have missing colours from $\{c_0, c_1\}$, so all three are endpoints of $H$. A single connected component of maximum degree $2$ has at most $2$ endpoints ($0$ for a cycle, $2$ for a path). So $C$ has at most two endpoints, but we have exhibited three distinct vertices ($x$, $v_1$, $v_k$ are distinct: $v_1 = v \neq x$ by the edge $xv$, and $v_k \neq v_1$ since the $v_i$ are distinct) each of which is an endpoint. This contradiction rules out the sub-case. [guided] The Kempe chain argument is the climax: we classify where $v_1$ and $v_k$ sit relative to $x$ in the $\{c_0, c_1\}$-subgraph $H$, and in every case either construct the missing colouring or derive a contradiction. **Why paths or even cycles?** $H$ uses only two colours. Proper colouring forces each vertex to have at most one edge of each colour in $H$, so $H$-degree is at most $2$. A graph with all vertices of degree $\leq 2$ has components that are paths or cycles. A cycle in $H$ must alternate $c_0$ and $c_1$, forcing even length. **Why are $x$, $v_1$, $v_k$ all endpoints of their $H$-components?** Each has exactly one of $c_0, c_1$ missing: $x$ has $c_0$ missing (and $c_1$ present on $xv_2$); $v_1$ and $v_k$ have $c_1$ missing. A vertex of $H$-degree $2$ has both $c_0$ and $c_1$ present on incident edges, so our three vertices cannot be interior vertices of $H$. **Why does being in the same component lead to contradiction?** A component of $H$ is a path or an even cycle. A cycle has zero endpoints — but $x$ is an endpoint, so $C$ is a path. A path has exactly two endpoints. But $\{x, v_1, v_k\}$ are three distinct endpoints — contradiction. **What do the Kempe swaps actually achieve?** They redistribute the $c_0 / c_1$ colouring on a specific component without touching the rest of $G$. The crucial property: if $x$ is not in the swapped component, then no edge incident to $x$ changes colour. This lets us manufacture "$c_0$ missing at $v_1$" or "$c_0$ missing at $v_k$" while preserving everything else we need. In every case (the two "different component" sub-cases) we complete the colouring. The "same component" sub-case yields a contradiction, meaning we are never in that sub-case. So the colouring can always be extended, completing the inductive step. [/guided] [/step] [step:Combine to conclude $\chi'(G) \in \{\Delta(G), \Delta(G) + 1\}$] By the induction, every graph $G$ satisfies $\chi'(G) \leq \Delta(G) + 1$. Combined with the lower bound $\chi'(G) \geq \Delta(G)$ from the first step, we have \begin{align*} \Delta(G) \leq \chi'(G) \leq \Delta(G) + 1, \end{align*} so $\chi'(G) \in \{\Delta(G), \Delta(G) + 1\}$, as claimed. [/step]