6
$\begingroup$

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?

  • 7
    Apply Dirac's theorem three times. Your 5-regular subgraph is the first two Hamiltonian cycles plus alternating edges from the third.2011-01-11
  • 7
    Thank you so much!!! But why didn't you post it as an answer? At first I didn't even notice the comment.2011-01-11

1 Answers 1