A class 2 graph is a simple graph whose edge chromatic number equals 
, where 
is its maximum vertex
degree. Vizing's theorem states that a simple graph can be edge-colored
in either 
or 
colors.
Class 2 graphs include the Petersen graph, complete graphs 
for 
, 5, 7, ..., and the snarks.
All regular graphs with at least one graph edge and an odd number of vertices are class 2 by parity. Such graphs necessarily have even vertex degree.
A sufficient condition for a graph 
to be class 2 is
 |
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 nonisomorphic class 2 simple graphs on 
,
2, ... vertices are 0, 0, 1, 1, 6, 11, 50, 131, 1131,
... (OEIS A099437).
Similarly, the numbers of nonisomorphic connected class 2 simple graphs on 
, 2, ... vertices are 0,
0, 1, 0, 4, 3, 32, 67, 930, ... (OEIS A099438;
Royle).
