An overfull graph is a finite simple graph 
satisfying
 |
where 
is its edge count, 
its vertex count, 
its maximum vertex
degree, and 
is the floor function (Jarnicki et al. 2017,
p. 428).
Every overfull graph is a class 2 graph. Each color class of an edge coloring is a matching,
so it contains at most 
edges. Consequently, 
colors cannot cover all 
edges, while Vizing's
theorem guarantees an edge coloring with at
most 
colors (Jarnicki et al. 2017, p. 428).
An overfull graph has odd vertex count, since the handshaking lemma gives
, which rules out the defining
inequality when 
is even. Every regular
graph with positive vertex degree and odd vertex count is overfull. Examples include the complete
graph 
and cycle graph 
for every positive
integer 
.
