Sign up ×
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|cite|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.