Extremal examples for a folklore lemma on subgraphs of large minimum degree It's a well known fact that a graph $G$ of average degree $d$ has a subgraph $G'$ of minimum degree at least $d/2$ and that the constant $1/2$ cannot be improved. The proof I know, which proceeds by peeling away low degree vertices, doesn't seem to characterise, in any nice way, the extremal examples for which the constant $1/2$ cannot be improved.
So my question is, what do extremal examples "look like"? Is there a simple characterisation? If not, I'd love to see any interesting constructions/families which give infinitely many extremal examples for a given value of $d$.
 A: Grids. (for one example only)
The grid $\overbrace{P_m \Box P_m \Box \cdots \Box P_m}^k$ has average degree about $2k$ as $m \rightarrow \infty$, but any subgraph seems to have to include a "corner" point of degree $\le k$.  I haven't thought too hard about how to make this precise.  
And sorry: I don't have the graph theory expertise to fully characterize the extremal examples.  What seems to make this argument work (provided I'm not wrong) is that the grid has a natural embedding in $\mathbb{R}^k$.
A: Another class of examples is given by trees.  A tree on $n$ vertices has $n-1$ edges, and thus has average degree $2 - 2/n$.  However, any subgraph must contain leaves, and thus has minimum degree $1$.
One may make the average/minimum degree arbitrarily large by `blowing up' the tree: replace every vertex with an independent set of size $d$, and replacing every edge of the tree by a complete bipartite graph $K_{d,d}$ on the vertices of the independent sets corresponding to the endpoints of the edge.  This blow-up now has $nd$ vertices and $(n-1)d^2$ edges, and so has average degree $2d - 2d/n$.  However, in any subgraph the vertices from the independent sets corresponding to leaves can have degree at most $d$.
My initial construction for an example with large minimum degree was the complete unbalanced bipartite graph $K_{\alpha n,n}$ for $\alpha \rightarrow 0$, but this corresponds to the blow-up of the tree $K_{1,1/\alpha}$ (by the factor $d = \alpha n$).
I am afraid I do not have a more general answer at this point!
A: I believe that David Eppstein's construction is basically the whole story. 
So for $0 <\epsilon \leq 1/2 $, call a graph 'bad' if it fails to have a subgraph with min degree $> (1/2 +\epsilon)d$.
Now Eppstein's construction restated:
" Build a graph on $1,...,n$ by visiting each vertex $i= 1,2.. $ and, at each stage, join $i$ to $(1/2 + \epsilon(i))d $ additional vertices among $\{ i+1, \ldots ,n \} $" 
Where $|\epsilon(i)| \leq \epsilon$ and $\sum \epsilon(i) = 0$. One thinks of this $\epsilon(i)$ as the 'noise' allowed by the $\epsilon$-room that we have. 
The average vertex has $d/2$ neighbors ahead of it and was hit 
by $d/2$ edges from previous vertices so the average degree is $d$. Of course, there are some issues at the boundary but this does not affect the average if we take n large.
Now we show that every 'bad' graph is constructed in this way. Obverse that bad graphs are the ones that are reduced to the empty graph by the process:
"If there is a vertex of degree $\leq (1/2 + \epsilon)d$ remove it. Otherwise, STOP".
Thus for a bad graph,we get an ordering of the vertices $v_1,v_2,...,v_n$ (taking in the order removed by the process) so that 
$v_i$ has at most $(1/2 + \epsilon)d$ edges forward to $v_{i+1}, \ldots v_n$. If the number of forward edges of $v_i$ is $(1/2 + \epsilon(i))d$ then $\sum \epsilon(i)=0$ holds by the fact the average degree is $d$.
A: If $G$ and $H$ are both extremal graphs (possibly for different values of $d$) then their Cartesian product is another extremal graph for the sum of the degrees. So the grid example is just a Cartesian product of paths, and you can similarly take the Cartesian product of trees.
A much more general way of constructing graphs with this property, which allows some vertices to have high degree: form a sequence of $n$ vertices and connect each vertex arbitrarily to $d/2$ later vertices in the sequence. Then, in any subset of vertices, the first vertex will have degree $d/2$, but (for $n$ sufficiently large relative to $d$) the average degree will be close to $d$.
