Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a graph $G$ with $\varepsilon(G)\ge k \in \mathbb{N}$ , find a minor $H\prec G$ such that $\delta(H)\ge k\ge |H|/2$.

Where $\varepsilon(G)$ is $|E(G)|/|V(G)|$, and $\delta(H)$ is the minimun degree of $G$.

This is the exercise 20 of the four edition of Graph Theory of Reinhard Diestel 2010.

share|improve this question
I suppose $\delta$ is the smallest degree, but what is $\varepsilon$? –  Chris Eagle Jan 31 '13 at 21:15
@Chris in Diestel's book $\varepsilon(G) = |E(G)|/|V(G)|$. Equivalently, $\varepsilon(G)$ is half of the average degree of $G$. –  Andrew Uzzell Feb 1 '13 at 12:57
The exercise can be found on page 197 in chapter 7 about extremal graph theory. –  Moritz Feb 25 at 0:12

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.