# On structure of graphs with average degree equal to maximum average degree

For a simple graph $$G$$, the $$\text{average-degree}(G)=|E(G)|/|V(G)|$$ and
the maximum average degree $$\text{mad}(G)=\max\{\text{average-degree}(H)\colon H \text{ is a subgraph of } G\}$$.

If $$\text{average-degree}(G)=\text{mad}(G)$$, what can we say about the structure of $$G$$?

Clearly, $$\text{average-degree}(G)=\text{mad}(G)$$ for every regular graph $$G$$. I suppose the graph being regular is not a necessary condition.

Context: Both parameters are equal for extremal graphs in some graph coloring problems.

• Isn't this class of bounded arboricity graphs? Or similarly class of bounded degeneracy graphs? Feb 25, 2022 at 6:55

For graph coloring, this property seems to have limited use. In particular, there is a reduction from any graph $$G$$ to a graph $$G'$$ that satisfies this property and $$\chi(G') = \chi(G)+1$$, where $$\chi(G)$$ denotes the chromatic number of $$G$$. The reduction is as follows:
Denote $$n = |V(G)|$$. Construct $$G'$$ by adding $$n$$ new vertices, each connected to every vertex of $$V(G)$$ but not to each other. Now, $$\chi(G') = \chi(G)+1$$ because the new vertices need an additional color but only one additional color suffices. I claim that $$G'$$ has the average degree property. Let $$G'[X]$$ be the induced subgraph of $$G'$$ with the highest average degree. I claim that $$G'[X] = G'$$. Let $$A$$ denote the original vertices $$V(G)$$ and $$B$$ denote the added vertices. Now, the average degree of $$G'[X]$$ is strictly less than $$|A \cap X|$$, because each vertex in $$B \cap X$$ contributes $$|A \cap X|$$ edges, and after counting edges adjacent to $$B \cap X$$, the vertices in $$A \cap X$$ contribute strictly less than $$|A \cap X|$$ edges. Now, if $$X \cap B \neq B$$, we could add a vertex in $$B$$ to $$X$$, contributing $$|A \cap X|$$ new edges, and therefore increasing average-degree. Therefore $$X$$ must contain $$B$$. Suppose $$X \cap A \neq A$$. Now, as $$B \subseteq X$$, adding a vertex of $$A$$ to $$X$$ contributes at least $$|B| > |A \cap X|$$ new edges, and therefore increases the average degree. Therefore $$X$$ must contain both $$A$$ and $$B$$, so $$G'[X] = G'$$.