  Let $G=(V,E)$ be a multigraph of maximum degree $\Delta$. The edges of $G$
can be colored with at most $\frac{3}{2}\Delta$ colors by Shannon's theorem. We
study lower bounds on the size of subgraphs of $G$ that can be colored with
$\Delta$ colors.
  Shannon's Theorem gives a bound of
$\frac{\Delta}{\lfloor\frac{3}{2}\Delta\rfloor}|E|$. However, for $\Delta=3$,
Kami\'{n}ski and Kowalik [SWAT'10] showed that there is a 3-edge-colorable
subgraph of size at least $\frac{7}{9}|E|$, unless $G$ has a connected
component isomorphic to $K_3+e$ (a $K_3$ with an arbitrary edge doubled). Here
we extend this line of research by showing that $G$ has a $\Delta$-edge
colorable subgraph with at least
$\frac{\Delta}{\lfloor\frac{3}{2}\Delta\rfloor-1}|E|$ edges, unless $\Delta$ is
even and $G$ contains $\frac{\Delta}{2}K_3$ or $\Delta$ is odd and $G$ contains
$\frac{\Delta-1}{2}K_3+e$. Moreover, the subgraph and its coloring can be found
in polynomial time.
  Our results have applications in approximation algorithms for the Maximum
$k$-Edge-Colorable Subgraph problem, where given a graph $G$ (without any bound
on its maximum degree or other restrictions) one has to find a
$k$-edge-colorable subgraph with maximum number of edges. In particular, for
every even $k \ge 4$ we obtain a $\frac{2k+2}{3k+2}$-approximation and for
every odd $k\ge 5$ we get a $\frac{2k+1}{3k}$-approximation. When $4\le k \le
13$ this improves over earlier algorithms due to Feige et al. [APPROX'02]
