Skip to main content
2 of 5
(4,3) counterexample
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$.


With $x=3$ and $b=4/3$ we have a counterexample, that is, a $(3,4)$-biregular graph that has no $3$-regular subgraph.

(3,4)-biregular graph with no 3-regular subgraph

This example is Figure 2 in Asratian et al. (2009). They note that it has no full $3$-regular subgraph (full meaning "one that covers all of the $4$-degree vertices"), but we can in fact find that it has no $3$-regular subgraph at all. It suffices to consider all $2^8-1=255$ nonempty subsets of the $3$-degree vertices (lower layer); in each case, take the subgraph of those vertices and all their neighbors; and observe that in all cases the resulting subgraph is noncubic. (This was, of course, a straightforward computational way; surely there are finer methods.)

Asratian, Armen S.; Casselgren, Carl Johan; Vandenbussche, Jennifer; West, Douglas B., Proper path-factors and interval edge-coloring of (3,4)-biregular bigraphs, J. Graph Theory 61, No. 2, 88-97 (2009). ZBL1198.05037.

Jukka Kohonen
  • 4.2k
  • 2
  • 21
  • 49