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.

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).

See also Class 1 Graph ,

Petersen Graph ,

Snark ,

Vizing's
Theorem
Portions of this entry contributed by Ed
Pegg, Jr. (author's link )

Portions of this entry contributed by Stan
Wagon

Explore with Wolfram|Alpha
References Royle, G. "Class 2 Graphs." http://school.maths.uwa.edu.au/~gordon/remote/graphs/#class2 . Sloane, N. J. A. Sequences A099437 and A099438 in "The On-Line Encyclopedia of Integer
Sequences." Referenced on Wolfram|Alpha Class 2 Graph
Cite this as:
Pegg, Ed Jr. ; Wagon, Stan ; and Weisstein, Eric W. "Class 2
Graph." From MathWorld --A Wolfram Web Resource. https://mathworld.wolfram.com/Class2Graph.html

Subject classifications More... Less...