Skip to main content
1 of 5
Jukka Kohonen
  • 4.2k
  • 2
  • 21
  • 49

Let's cover one more easy case, extending your list of trivial cases.

If $x=2$ and $b \ge 1$, then the claim is true.

Proof: If $G$ contains a cycle, there is your $2$-regular subgraph. Otherwise $G$ is cycle-free, so it is a forest. A finite forest has some leaves, that is, vertices of degree $1$. But this is impossible since we have assumed that all vertices have degree $x=2$ or $bx \ge 2$.

Jukka Kohonen
  • 4.2k
  • 2
  • 21
  • 49