Maximal $k$-Edge-Colorable Subgraphs, Vizing's Theorem, and Tuza's Conjecture

We prove that if $M$ is a maximal $k$-edge-colorable subgraph of a multigraph $G$ and if $F=\{v\in V(G):d_M(v)\le k-\mu (v)\}$, then $d_F(v) \leq d_M(v)$forall$v \in F$\mathrm{.}(When$G$isasimplegraph,theset$F$ is just the set of vertices having degree less than $k$ in $M$.) This implies Vizing’s Theorem as well as a special case of Tuza’s Conjecture on packing and covering of triangles. A more detailed version of our result also implies Vizing’s Adjacency Lemma for simple graphs.