Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $G$ be a simple graph such that

  • $|V(G)|$ is even
  • $\delta(G) \gt \tfrac12|V(G)|+3$ where $\delta(G)$ is the minimum degree of a vertex in $G$.

The question is to prove there exists a $5$-regular spanning subgraph of $G$.

I'm trying to figure this out for at least 10 hours, but no avail. :(

The only thing I've managed to do is prove that $|V(G)| \ge 8$ and that $G$ is Hamiltonian (via Dirac's theorem).

Any ideas?

share|cite|improve this question
Apply Dirac's theorem three times. Your 5-regular subgraph is the first two Hamiltonian cycles plus alternating edges from the third. – Chris Eagle Jan 11 '11 at 7:37
Thank you so much!!! But why didn't you post it as an answer? At first I didn't even notice the comment. – user5596 Jan 11 '11 at 8:23

This is a fleshed-out version of Chris Eagle's answer/comment, except that we could avoid the machinery of Dirac's theorem. I recall a result from a related question of mine:

Theorem A. If $|V(G)|$ is even and $\delta(G) \geqslant \frac{|V(G)|}{2}$, then $G$ contains a perfect matching.

In fact, we will not need a proof of the above theorem, just its statement. [That said, I encourage you to read joriki's elegant direct proof that just uses Hall's theorem.]

The present question is a generalization of this theorem. Define a $b$-factor of $G$ to be any spanning subgraph $H$ of $G$ that is $b$-regular. (Plug in $b = 5$ to get the desired statement.)

Theorem B. If $|V(G)|$ is even and $\delta(G) \geqslant \frac{|V(G)|}{2} + b -1$, then $G$ contains $b$-factor.

To prove this, we repeatedly apply "Theorem A" $b$ times, each time deleting the resulting perfect matching from the graph. In each iteration, each degree goes down by $1$, so the condition that $\delta \geqslant \frac{|V(G)|}{2}$ is preserved at each of the $b$ steps.

share|cite|improve this answer

Your Answer


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