Return to Answer

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.

Here is the graph drawing:

And here is its graph6 string:

T@C?GG@COC?O?OC_AO?a??oBk_E?{@O[b?`g

The claim does not hold. 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 (with integer $b$), and it's unique for 21 vertices.

Here is the graph drawing:

And here is its graph6 string:

T@C?GG@COC?O?OC_AO?a??oBk_E?{@O[b?`g

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.

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.

Here is the graph drawing:

And here is its graph6 string:

T@C?GG@COC?O?OC_AO?a??oBk_E?{@O[b?`g

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.

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.