Skip to main content
2 of 4
added 113 characters in body
Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152

The answer is No. Here is a counterexample with $a=7$, $b=2$ and $x=3$.

This graph has partite sets of sizes $|U|=14$ and $|V|=7$. Labeling vertices of $V$ as $1,2,\dots,7$, the vertices in $U$ (each of degree 3) are connected to $$127,\ 127, 136,\ 136,\ 145,\ 157,\ 235,\ 246,\ 246,\ 256,\ 347,\ 347,\ 356, 457.$$

I have computationally verified that this graph has no 3-regular subgraph. It is the smallest counterexample with respect to the total number of vertices, and it's unique for 21 vertices.

Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152