Given a graph 
, the maximum average degree, sometimes denoted 
, is the maximum average degree over all nonempty subgraphs
of 
.
It is therefore given by
 |
(1)
|
Because deleting edges cannot increase average degree, this is equivalent to maximizing over all nonempty vertex-induced subgraphs, i.e.,
![mad(G)=max_(emptyset!=S subset= V(G))(2|E(G[S])|)/(|S|).](/images/equations/MaximumAverageDegree/NumberedEquation2.svg) |
(2)
|
The maximum average degree is closely related to the pseudoarboricity. If 
denotes the pseudoarboricity of 
, then
![p(G)=[(mad(G))/2].](/images/equations/MaximumAverageDegree/NumberedEquation3.svg) |
(3)
|
It is also closely related to the arboricity 
and the fractional
arboricity. In particular,
 |  | ![[max_(H subset= G, |V(H)|>=2)(|E(H)|)/(|V(H)|-1)],](/images/equations/MaximumAverageDegree/Inline9.svg) |
(4)
|
 |  |  |
(5)
|
where 
is the fractional arboricity.
Some basic examples are
 |
(6)
|
 |
(7)
|
 |
(8)
|
 |
(9)
|
for a tree 
on 
vertices, and
 |
(10)
|
This parameter is important in structural graph theory, graph coloring, and the study of sparse graphs.
For example, if 
is a planar graph on 
vertices, then Euler's
formula implies
 |
(11)
|
Likewise, every triangle-free planar graph satisfies
 |
(12)
|
More generally, a bound of the form 
is often used to guarantee that some nonempty subgraph
of 
contains a vertex of degree at most 
, which makes maximum average degree a useful tool in degeneracy
arguments and discharging proofs.
