Maximum Average Degree

The maximum average degree of a nonempty finite graph , sometimes denoted , is the maximum average degree over all nonempty subgraphs of . It is therefore given by

(1)

For a fixed vertex set, deleting edges cannot increase average degree, so it is equivalent to maximize over all nonempty vertex-induced subgraphs, i.e.,

(2)

For the following characterizations and bounds, is assumed to be a simple graph. The maximum average degree is closely related to the pseudoarboricity. If denotes the pseudoarboricity of , then

(3)

where is the ceiling function. It is also closely related to the arboricity and the fractional arboricity. For a graph with at least two vertices,

			(4)
			(5)

where is the fractional arboricity. Both quantities are zero for graphs with at most one graph vertex.

Some basic examples are, for integers ,

(6)

(7)

and, for ,

(8)

For a tree on vertices,

(9)

and, for positive integers 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 polyhedral formula implies

(11)

Likewise, every triangle-free planar graph satisfies

(12)

More generally, for a positive integer , a bound of the form guarantees that every nonempty subgraph of contains a vertex of degree at most . This makes maximum average degree a useful tool in degeneracy arguments and discharging proofs.

Grzesik et al. (2026) proved that, for positive real numbers and , the condition guarantees disjoint subsets and with and

			(13)
			(14)

Here and are vertex-induced subgraphs, and the maximum average degree of the null graph is taken to be zero. Repeated application gives the analogous decomposition into disjoint subsets for any finite list of positive bounds. Empty subsets are allowed. This proves the maximum average degree partition conjecture and yields sharp clustered coloring results. Grzesik et al. (2026) state that ChatGPT-5.6 Sol suggested the potential function, but that the final proof was developed by the authors.