Vizing's theorem states that a graph can be edge-colored in either 
or 
colors, where 
is the maximum vertex
degree of the graph. A graph with edge chromatic
number equal to 
is known as a class 2 graph.
Class 2 graphs include the Petersen graph, complete graphs 
for 
, 5, 7, ..., and the snarks.
All non-empty regular graphs with an odd number of nodes 
are class 2 by parity. Such graphs automatically have an even number of edges per
vertex.
A graph is trivially class 2 if the maximum independent edge sets are not large enough to cover all edges. In particular, a graph 
is trivially class 2 if
 |
where 
is the matching number, 
the maximum vertex
degree, and 
the edge count of 
.
The following table summarizes some named class 2 graphs.
graph  |  |
| triangle graph | 3 |
| pentatope graph | 5 |
| Petersen graph | 10 |
| first Blanuša snark | 18 |
| second Blanuša snark | 18 |
| Robertson graph | 19 |
flower
snark  | 20 |
| 25-Grünbaum graph | 25 |
| Doyle graph | 27 |
| double star snark | 30 |
| Szekeres snark | 50 |
| McLaughlin graph | 275 |
The numbers of simple class 2 graphs on 
, 2, ... nodes are 0, 0, 1, 1, 6, 11, 50, 131, 1131, ...
(OEIS A099437).
Similarly, the numbers of simple connected class 2 graphs are 0, 0, 1, 0, 4, 3, 32, 67, 930, ... (OEIS A099438; Royle).
