Vizing’s theorem
Definitions and notation
In a graph or multigraph^{} $G$, let $\rho (\mathrm{\text{v}})$ denote the valency^{} of vertex (node) v, and let $\rho (G)$ denote the largest valency in $G$ (often written just $\rho $ on its own, $\mathrm{\Delta}(G)$ is another common notation).
Let the multiplicity^{} $\mu (\mathrm{\text{v}},\mathrm{\text{w}})$ of vertices (nodes) v and w be the number of parallel edges that link them, and here too let $\mu (G)$ be the largest multiplicity in $G$. A graph is a multigraph for which $\mu (G)=1$.
An edge coloring^{} of a (multi)graph $G$ is a mapping from the set $E$ of its edges to a set $K$ of items called colors, in such a way that at any vertex v, the $\rho (\mathrm{\text{v}})$ edges there all have a different color. An edge$k$coloring^{} is an edgecoloring where $K=k$.
Note that a loop (an edge joining v to itself) accounts for two of the $\rho (\mathrm{\text{v}})$ edges at v and cannot have a color different from itself, so edgecolorings as defined here do not exist for pseudographs^{} (structures^{} that are allowed to have loops).
The chromatic index (aka edgechromatic number) ${\chi}^{\prime}(G)$ is the smallest number $k$ for which an edge$k$coloring of $G$ exists. This now standard notation is analogous to the chromatic number^{} $\chi (G)$ which refers to vertex coloring.
Vizing’s theorem
For any multigraph $G$ (this includes graphs), we have of course
$${\chi}^{\prime}(G)\u2a7e\rho (G)$$ 
immediately from the definition. Surprisingly though, we also have
Theorem (Vizing)$$ For any graph $G$,
$${\chi}^{\prime}(G)\u2a7d\rho (G)+1$$ 
This celebrated theorem was proved by V. G. Vizing in 1964 while still a graduate student (at Novosibirsk). It is a special case of
Theorem (Vizing)$$ For any multigraph $G$,
$${\chi}^{\prime}(G)\u2a7d\rho (G)+\mu (G)$$ 
(edgecoloring of multigraphs is the subject of Vizing’s doctoral thesis, 1965). The theorem was proved independently by R. P. Gupta in 1966; nowadays various versions of the proofs exist. A key rôle is played by connected subgraphs^{} $H(a,b)$ of colors $a$ and $b$ that cannot be extended further. They are analogous to Kempe chains^{} in face or vertex colorings, but have a simpler structure: they are either paths or closed paths (the latter of even length). http://planetmath.org/node/6932See here for a proof (in the case of graphs).
Ore [Ore67] gives a sharper bound for multigraphs. Let the enlarged valency ${\rho}^{+}(\mathrm{\text{v}})$ be given by
$${\rho}^{+}(\mathrm{\text{v}})\stackrel{\text{def}}{=}\rho (\mathrm{\text{v}})+\underset{\mathrm{w}}{\mathrm{max}}\mu (\mathrm{\text{v}},\mathrm{\text{w}})$$ 
where w can be taken over all vertices of the graph; it effectively only ranges over those adjacent to v (as $\mu (\mathrm{\text{v}},\mathrm{\text{w}})$ is zero for the others). Again, let ${\rho}^{+}(G)$ denote the maximum enlarged valency occurring in $G$. Now
Theorem (Ore)$$ For any multigraph $G$,
$${\chi}^{\prime}(G)\u2a7d{\rho}^{+}(G)$$ 
Shannon’s theorem
The following theorem was proven in 1949 by Claude E. Shannon. He also gives examples, for any value of $\rho $, of multigraphs that actually attain the bound, the socalled Shannon graphs: they have three vertices, with $\mu (\mathrm{\text{a}},\mathrm{\text{b}})=\mu (\mathrm{\text{a}},\mathrm{\text{c}})=\lfloor \rho /2\rfloor $ and $\mu (\mathrm{\text{b}},\mathrm{\text{c}})=\lceil \rho /2\rceil $.
Theorem (Shannon)$$ For any multigraph $G$,
$${\chi}^{\prime}(G)\u2a7d\lfloor \frac{3}{2}\rho (G)\rfloor $$ 
While giving a much worse bound for graphs, it gives for some multigraphs a better bound than Vizing’s theorem. Nevertheless, it is also possible to prove it from the latter [FW77].
Only in the context of graph colorings^{} is Shannon’s theorem understood to refer to the one here; in the wider world the term tends to refer to any of his fundamental theorems in information theory.
Here too Ore [Ore67] gives a sharper bound based on the maximum of a local expression. Let $\sigma (\mathrm{\text{v}})$ be 0 if v has fewer than two neighbours, and otherwise
$$\sigma (\mathrm{\text{v}})\stackrel{\text{def}}{=}\underset{{\mathrm{v}}^{\prime},{\mathrm{v}}^{\prime \prime}}{\mathrm{max}}(\rho (\mathrm{\text{v}})+\rho ({\mathrm{\text{v}}}^{\prime})+\rho ({\mathrm{\text{v}}}^{\prime \prime}))$$ 
where ${\mathrm{\text{v}}}^{\prime}$ and ${\mathrm{\text{v}}}^{\prime \prime}$ range over all pairs of distinct neighbours of v. Again, let $\sigma (G)$ be its largest value in the graph.
Theorem (Ore)$$ For any multigraph $G$,
$${\chi}^{\prime}(G)\u2a7d\mathrm{max}(\rho (G),\lfloor \frac{1}{2}\sigma (G)\rfloor )$$ 
Chromatic class
Vizing’s theorem has the effect of placing each multigraph $G$ in one of the classes 0, 1, 2, … $\mu (G)$ where the class number is ${\chi}^{\prime}(G)\rho (G)$.
For graphs it means they split into just two classes: those that can be edgecolored in $\rho (G)$ colors and those that need $\rho (G)+1$ colors. The logical name for them would be class 0 and class 1; unfortunately the standard terminology is class 1 and 2 (or I and II).
Class I (graphs that can be edge$\rho $colored) contains among others

•
single $n$cycles for even $n$ ${}^{\u2020}$

•
complete graphs^{} ${K}_{n}$ for even $n$ ${}^{\u2021}$

•
bipartite graphs^{} (this is König’s theorem, 1916)

•
bridgeless planar trivalent graphs (fourcolor theorem via Tait coloring^{})

•
planar graphs^{} with $\rho (G)\u2a7e8$ (by another theorem of Vizing)

•
planar graphs with $\rho (G)\u2a7e6$?? (conjecture of Vizing)
Class II (graphs that need $\rho +1$ colors) contains among others

•
single $n$cycles for odd $n$ ${}^{\u2020}$

•
complete graphs ${K}_{n}$ for odd $n$ ${}^{\u2021}$

•
${K}_{n}$ for odd $n$ with a few edges missing (by a couple of theorems)

•
trivalent graphs with a bridge ${}^{\mathrm{\P}}$
but the general classification problem has thus far eluded the best efforts of Vizing and many others. There are interesting links here with polyhedral decompositions (aka cyclic double covers) and embeddings^{} in surfaces.
A(n edge)critical graph is a connected graph of class II but such that removing any of its edges makes it class I. As often in graph theory^{}, such a minimality condition imposes a certain amount of structure on the graph. There are conjectures…
Almost all graphs are in class I
Let $\mathrm{\#}{G}_{n}$ be the number of graphs with $n$ vertices, and $\mathrm{\#}{G}_{n}^{\mathrm{I}}$ the number of them in class I.
Theorem (P. Erdős and R. J. Wilson)$$
$$\underset{n\to \mathrm{\infty}}{lim}\frac{\mathrm{\#}{G}_{n}^{\mathrm{I}}}{\mathrm{\#}{G}_{n}}=1$$ 
So graphs of class II get relatively rarer for larger graph sizes. The absolute numbers do still increase. For cubic graphs for instance, we saw every one with a bridge is in class II. Bridgeless cubic graphs of class II are a bit thinner on the ground. By the fourcolor theorem, via Tait coloring, we know all of them are nonplanar. Rarer still are those of them with girth at least five (and some nontriviality conditions); they are so hard to find that Martin Gardner dubbed them snarks. The Petersen graph^{} is one, and a few infinite^{} families of snarks have been found.
$\u2020\mathit{\hspace{1em}}$ $\rho =2$, so an edge$\rho $coloring must use alternating colors. For odd $n$ that’s impossible.
$\u2021\mathit{\hspace{1em}}$ $\rho =n1$, note it is also the valency of every vertex. Fix two colors $a$ and $b$. A Kempe chain $H(a,b)$ can only terminate at a vertex where one of those colors is missing but in ${K}_{n}$ we cannot afford to miss any color at any vertex, so every $H(a,b)$ is a cycle of even length and together they visit all $n$ vertices. For odd $n$ that’s impossible. For even $n$ there are ways to construct the coloring (try it).
$\mathrm{\P}$ $\rho =3$ and again the valency of every vertex. For the same reason as in the previous note, every $H(a,b)$ or $H(c,a)$ or $H(b,c)$ is a cycle. Every edge must be in two such, but a bridge cannot be part of a cycle.
References
 1

Ore67
Oystein Ore, The FourColor Problem,
Acad. Pr. 1967, ISBN 0 12 528150 1
Long the standard work on its subject, but written before the theorem was proven. Has a wealth of other graph theory material, including proofs of (improvements of) Vizing’s and Shannon’s theorems. 
FW77
S. Fiorini and R. J. Wilson,
Edgecolourings of graphs, Pitman 1977,
ISBN 0 273 01129 4
The first ever book devoted to edgecolorings, including material previously found only in Russian language^{} journal articles. Has proofs of Vizing’s and Shannon’s theorems. 
SK77
Thomas L. Saaty and Paul C. Kainen,
The FourColor Problem: assaults and conquest,
McGrawHill 1977; repr. Dover 1986, ISBN 0 486 65092 8
Wonderfully broad, not only focussing on the usual route to the AppelHaken proof but also giving lots of other material. 
Wil02
Robert A. Wilson,
Graphs, Colourings and the Fourcolour Theorem,
Oxford Univ. Pr. 2002, ISBN 0 19 851062 4 (pbk),
http://www.maths.qmul.ac.uk/ raw/graph.htmlhttp://www.maths.qmul.ac.uk/ raw/graph.html
(errata &c.)
A good general course in graph theory, with special focus on the fourcolor theorem and details of the AppelHaken proof. Has proof of Vizing’s theorem.
Title  Vizing’s theorem 
Canonical name  VizingsTheorem 
Date of creation  20130322 15:10:36 
Last modified on  20130322 15:10:36 
Owner  marijke (8873) 
Last modified by  marijke (8873) 
Numerical id  11 
Author  marijke (8873) 
Entry type  Theorem 
Classification  msc 05C15 
Related topic  TaitColoring 
Defines  edge coloring 
Defines  edge$k$coloring 
Defines  chromatic index 
Defines  edgechromatic number 
Defines  class I 
Defines  class II 
Defines  class 1 
Defines  class 2 
Defines  edgecritical graph 
Defines  enlarged valency 
Defines  snark 