Class 2 Graph

Vizing's theorem states that a graph can be edge-colored in either Delta or Delta+1 colors, where Delta is the maximum vertex degree of the graph. A graph with edge chromatic number equal to Delta+1 is known as a class 2 graph.

Class 2 graphs include the Petersen graph, complete graphs K_n for n=3, 5, 7, ..., and the snarks.

All non-empty regular graphs with an odd number of nodes n>1 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 G is trivially class 2 if


where nu(G) is the matching number, Delta(G) the maximum vertex degree, and m the edge count of G.

The following table summarizes some named class 2 graphs.


The numbers of simple class 2 graphs on n=1, 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


Royle, G. "Class 2 Graphs.", 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.

Subject classifications