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

CC BY-SA 4.0
2022-02-26T11:50:17.277Z
2022-02-26T11:50:17.277Z
Laakeri
<p>For a simple graph <span class="math-container">$G$</span>, the <span class="math-container">$\text{average-degree}(G)=|E(G)|/|V(G)|$</span> and<br />
the maximum average degree <span class="math-container">$\text{mad}(G)=\max\{\text{average-degree}(H)\colon H \text{ is a subgraph of } G\}$</span>.</p>
<p><em>If <span class="math-container">$\text{average-degree}(G)=\text{mad}(G)$</span>, what can we say about the structure of <span class="math-container">$G$</span>?</em></p>
<p>Clearly, <span class="math-container">$\text{average-degree}(G)=\text{mad}(G)$</span> for every regular graph <span class="math-container">$G$</span>. I suppose the graph being regular is not a necessary condition.</p>
<p>Context: Both parameters are equal for extremal graphs in some graph coloring problems.</p>

CC BY-SA 4.0
2022-02-25T06:55:33.967Z
Isn't this class of bounded arboricity graphs? Or similarly class of bounded degeneracy graphs?
Saeed
<graph-theory><co.combinatorics><extremal-combinatorics>
On structure of graphs with average degree equal to maximum average degree
Cyriac Antony
# On structure of graphs with average degree equal to maximum average degree

(Asked by: username_0 on 2022-02-25)

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.

**Tags:** graph-theory, co.combinatorics, extremal-combinatorics

> **Comments:**
> **username_1**: Isn't this class of bounded arboricity graphs? Or similarly class of bounded degeneracy graphs?  

---

## 1 answers

### Answer by username_2 on 2022-02-26. Score: 1

This question is a bit open-ended, but here are some observations:

Some non-regular graphs can have this property, for example all trees have this property.

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'$.


---

