Problem 1: In edge coloring, we assign colors to the edges of G so that all the edges incident to a vertex receive different colors. χ0(G) is the minimum number of colors required to edge color G.
Assume χ0(G) > ∆(G)+1 but for any edge xy, χ0(G−xy) = ∆+1. Prove that in every proper edge coloring of G−xy there exists a path from x to y in which the edges alternate between two colors. (We can use this fact to prove Vizing’s Theorem: χ0(G) ≤ ∆(G) + 1 by induction.)
Problem 2: Assume G is a ∆-regular multigraph, and assume ∆ is even. Prove that
