Talk:Vizing's theorem

Condition (1) in the proof is equivalent?

Suppose that no proper $(Δ+1)$ -edge-coloring of $G$ exists. This is equivalent to this statement:

(1) Let $xy \in E$ and $c$ be arbitrary proper $(Δ+1)$ -edge-coloring of $G - xy$ and $α$ be missing from $x$ and $β$ be missing from $y$ with respect to $c$ . Then the $α/β$ -path from $y$ ends in $x$ .

I am not entirely convinced that (1) is sufficient, i.e. (1) implies that no proper $(Δ+1)$ -edge-coloring of $G$ exists. Not entirely sure how you can restrict the coloring. What if $xy$ has some color $\gamma$ that is different from $\alpha$ and $\beta$ ?

I also checked the source and Diestel didn't mention anything about its sufficiency. DeyaoChen (talk) 01:20, 5 December 2024 (UTC)[reply]

Doesn't the following paragraph explain the equivalence? Russ Woodroofe (talk) 11:32, 6 December 2024 (UTC)[reply]

Yeah but I am not entirely convinced by the argument. Seems dubious. DeyaoChen (talk) 11:20, 7 December 2024 (UTC)[reply]

It looks ok to me. If a proper coloring exists, and we delete edge xy, then no alpha-beta path starting with the color of the deleted edge can connect the two vertices, because these paths always stop after zero edges. —David Eppstein (talk) 01:18, 11 December 2024 (UTC)[reply]

What if the graph is a cycle with alternating colored edges except one edge is a third color? Then after we delete the edge with the third color, we get a alpha-beta path. DeyaoChen (talk) 11:19, 11 December 2024 (UTC)[reply]

I saw the new edit. Sorry I was wrong. Now I see the logic. DeyaoChen (talk) 13:41, 11 December 2024 (UTC)[reply]