Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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).

share|improve this question
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
add comment

2 Answers

Here are some very minor and mostly negative observations in the k=2 case. Obviously a 2-degenerate subgraph in an n-vertex graph can have at most 2n-3 edges. So let's ask which graphs have 2-degenerate subgraphs with exactly 2n-3 edges. Vertices of degree at most 2 can force the answer to be "no". So let's assume minimum degree at least 3. And if a graph has c components, then every 2-degenerate subgraph has at most 2n-3c edges. So let's assume that our graph is connected. But still there are graphs for which every 2-degenerate subgraph has strictly less than 2n-3 edges. Let G be a connected graph with 6 vertices of degree 3 and n-6 vertices of degree 4. (There are many ways to construct such a graph, starting from K_{3,3}.) So the total number of edges is 2n-3, but the graph itself is not 2-degenerate. So there is no 2-degenerate subgraph of G with 2n-3 edges.

I am interested in this question, so if you know something else, then please email david.wood.42@gmail.com

share|improve this answer
add comment

Just a minor remark (that might be useful, who knows?)

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.

share|improve this answer
add comment

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.