Question: G is a graph with n$\ge$2 vertices an min degree $\delta$. Prove that G contains a spanning sub graph of a min degree $\delta$ with at most $(n-1)\delta$ edges.

Thoughts: For the induction step I've tried 4 different approaches:

  1. Removing the vertex with min degree, using the induction hypothesis and then bringing back the vertex and it's edges- that implied either min degree became lower or equal (and that was okay, as I could have bounded the new min degree with the old one), but If it increased I didn't know what to do.

  2. Removing the vertex with the max degree- That made sure (?) that the min degree won't increase, but then I couldn't bound the number of edges in the spanning sub graph.

  3. Removing a vertex which is a neighbor of a vertex with the min degree. This implies the n vertices sub graph will have a spanning subgraph with (n-1)($\delta$-1) edges. I can bring back at most n edges if the graph is simple, but this (n-1)($\delta$-1)+n is still less then the needed $n\delta$.

  4. Removing a vertex which is not a neighbor of a vertex with the min degree. I'm not sure I can do this, cause I can't prove that such vertex always exists. Also, to such a vertex I think I can add back more than $\delta$ edges which may turn to give me more than $n\delta$ edges in total.

  • $\begingroup$ For 3, why is it undesirable that $(n-1)(\delta-1)+n$ is less than $n\delta$? By the way, this is one of the best question write-ups I've ever seen. $\endgroup$ – Erick Wong Nov 30 '14 at 17:40
  • $\begingroup$ I think the questions means for the bound to be tight, doesn't it? I mean otherwise it would have been a different bound $\endgroup$ – jreing Nov 30 '14 at 17:42
  • $\begingroup$ That's kind of up to the author of the question in terms of writing style. I guess the upper bound you get from your argument is something like $(n - (\delta+1)/2) \delta$, which is more awkward to state than $(n-1)\delta$ (and the latter is still tight for $\delta = 0, 1$). $\endgroup$ – Erick Wong Nov 30 '14 at 18:17
  • $\begingroup$ i know its to late .... but i'm trying to solve this one too . i think we can solve it by using spanning trees of the graph . step 1 find spanning tree of the graph step 2 remove the edges selected for the tree from the original graph and name it $G'$ now repeat step 1 and 2 each time removing edges from $G$ and adding them to $G'$ we can repeat it $\delta$ times . so we get $(n-1) \cdot \delta$ edges in total in $G'$ (n-1 is number of edges in a tree) $\endgroup$ – Boris Morozov Jul 31 '15 at 10:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.