The lower bound $\chi' \geq \Delta$ is trivial. For the upper bound, we prove that any simple graph $G$ can be properly edge-colored with $\Delta + 1$ colors by an augmenting path argument.

Setup. Assume we have a partial proper edge-coloring $\phi$ with $\Delta + 1$ colors, and let $e = v_0v_1$ be an uncolored edge. We will recolor edges to accommodate $e$.

Fan construction. Build a fan at $v_0$: a sequence of distinct neighbors $v_1, v_2, \ldots, v_k$ of $v_0$ such that the color of edge $v_0 v_{j+1}$ is a color missing at $v_j$ for each $j$. Formally: let $c_j = \phi(v_0 v_j)$ for $j \geq 1$. Choose $v_{j+1}$ so that $c_{j+1}$ is missing at $v_j$ (i.e., $c_{j+1} \notin \phi(\text{edges at } v_j)$). Continue until no further extension is possible.

Key observations. When the fan cannot be extended, every color missing at $v_k$ is present at $v_0$ (otherwise we could extend). Since $\deg(v_0) \leq \Delta$ and we use $\Delta + 1$ colors, there is a color $\alpha$ missing at $v_0$.

Case 1: If $\alpha$ is also missing at some $v_j$ in the fan, then shift the fan: uncolor $v_0v_1$, recolor $v_0v_{j'}$ with the color of $v_0v_{j'+1}$ for $j' = 1, \ldots, j-1$, and color $v_0v_j$ with $\alpha$. Then color $v_0v_1$ with the free color.

Case 2: $\alpha$ is present at all $v_j$, and there is a color $\beta$ missing at $v_k$ but present at $v_0$. Consider the $\alpha\beta$-path starting at $v_k$: the maximal path alternating colors $\alpha$ and $\beta$ starting from $v_k$.

• If this path does not reach $v_0$: swap $\alpha$ and $\beta$ on this path. Now $\alpha$ is missing at $v_k$, reducing to Case 1 (after fan shifting).

• If the path reaches $v_0$: it arrives at $v_0$ through some $v_j$ (since $\beta = c_j$ for some $j$ in the fan). Now we cannot swap on this path directly. Instead, shift the fan only up to $v_j$ (recolor $v_0v_{j'}$ with $c_{j'+1}$ for $j'=1,\ldots,j-1$), making $\beta$ free at $v_0$. Then swap $\alpha,\beta$ on the path from $v_k$ (which no longer connects to $v_0$ through the recolored edge), making $\alpha$ free at $v_k$. Color $v_0v_1$ with a free color.

In all cases, we extend the coloring to include $e$. Starting from the empty coloring and adding edges one by one completes the proof. $\square$