[Solved] CSDS455 Homework 13-Edge coloring

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. χ⁰(G) is the minimum number of colors required to edge color G.

Assume χ⁰(G) > ∆(G)+1 but for any edge xy, χ⁰(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: χ⁰(G) ≤ ∆(G) + 1 by induction.)

Problem 2: Assume G is a ∆-regular multigraph, and assume ∆ is even. Prove that