[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, ⁰(Gxy) = +1. Prove that in every proper edge coloring of Gxy there exists a path from x to y in which the edges alternate between two colors. (We can use this fact to prove Vizings Theorem: ⁰(G) (G) + 1 by induction.)

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