Skip to main content
4 of 5
+context, relevant field
Jukka Kohonen
  • 4.2k
  • 2
  • 21
  • 49

With $x=2$ and $b \ge 1$ 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$ the claim is false. The following $(3,4)$-biregular graph 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.)

To provide some context (and to address the question "which mathematical fields are likely to be helpful"): It seems that regular subgraphs of biregular graphs are relevant in interval coloring, which is edge-coloring with certain constraints. Most results that I quickly found are in the direction "if there is a regular subgraph with so-and-so properties, then you have an interval coloring".

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