# Finding maximal k-degenerate subgraphs

Given a graph $G$, let $H$ be a $k$-degenerate (not necessarily induced) subgraph of maximal size. Are there any known lower bounds on $|E(H)|$ for particular classes of $G$ and values of $k$?

I've seen several papers on the subject, but only for induced subgraphs $H$. I'm particularly interested in the case where $k=2$ and $G$ is both regular and bipartite, but any additional information would be helpful.

(I'm aware of the naive lower bound found by arbitrarily removing edges until no vertex has degree $(k+1)$ or more...I'm looking for something better).

• what does $k$-degenerate means? – Dima Pasechnik Sep 24 '12 at 7:03
• @Dima - $k$-degenerate means that every subgraph has a vertex of degree at most $k$. Equivalently, repeatedly remove the vertex of minimum degree until the graph is gone; the degeneracy number of the graph is the biggest degree you saw along the way. – Gordon Royle Sep 24 '12 at 22:47

Any $2k$-edge-connected graph on $n$ vertices contains a spanning $(2k-1)$-degenerate subgraph on $k(n-1)$ edges.
Proof: by Nash-Williams, a $2k$-edge-connected graph contains $k$ edge-disjoint spanning trees. The spanning subgraph whose edge-set consists of the union of these $k$ spanning trees is $(2k-1)$-degenerate and contains $k(n-1)$ edges.