Skip to main content
2 of 5
This is one of those cases where the horizontal spacing is conspicuously different (and incorrect) when \left and \right| are omitted
Michael Hardy
  • 1
  • 12
  • 85
  • 126

Arboricity and average degree

Let $G$ be a graph on $>1$ vertices. Recall that its maximum average degree is defined to be $$M(G) = \max\left\{\frac{2\left|E_H\right|}{|V_H|} \colon H \subseteq G, |V_H| > 1\right\},$$ and its arboricity is equal to $$A(G) = \max\left\{\left\lceil\frac{|E_H|}{|V_H|-1}\right\rceil \colon H \subseteq G, |V_H| > 1\right\}.$$

In [https://arxiv.org/pdf/1802.05582.pdf, near the end of page 2] it is stated that "it is not difficult to show that $2A(G) - 2 \le \lceil M(G)\rceil$". However, I am not sure what is the reasoning.