Does an $(x, bx)$-biregular graph always contain a $x$-regular bipartite subgraph?

Question

I guess a discrete-mathematics-related question is still welcome in MO since I was new to the community and learned from this amazing past post. The following claim is a simplified and abstract form of the network problem I am working on in distributed computing.

N.B.: all the graphs mentioned below are simple and undirected.

TL;DR

Does an $(x, bx)$-biregular graph always contain a $x$-regular bipartite subgraph?

Notation and Claim

A biregular or semiregular bipartite graph is a bipartite graph $G = (U, V, E)$ where the vertices in each bipartition $U$ or $V$ have the same degree. An $(x, y)$-biregular graph is a biregular graph $G = (U, V, E)$ where all vertices in $U$ have degree $x$ and the ones in $V$ have degree $y$ (from Wikipedia). We have $x|U| = y|V|$ immediately.

Let $|U| = ab$ and $|V| = a$. Then $bx = y$ and $1 \leq x \leq a$.

Claim. An $(x, bx)$-biregular graph $G = (U, V, E)$ always contains at least one $x$-regular bipartite subgraphs.

And the beauty of the claim is that if it holds, we are guaranteed to keep removing such a subgraph from $G$ by recursively applying the claim — an $(x, bx)$-biregular graph $G = (U, V, E)$ is now decomposed into $b$ edge-disjoint $x$-regular bipartite subgraphs.

Here is a visual example with $a = 4$, $b = 3$ and $x = 2$ (hence $|U| = 12$ and $|V| = 4$). The edges with the same colour consist of a subgraph.

Some trivial cases:

1. When $x = a$, meaning $G$ is complete and biregular, the claim holds.
2. When $x = 1$, $G$ is disconnected but it is still the case.
3. When $b = 1$, $G$ is a $x$-regular bipartite graph itself.

Possible Areas

After a long time online searching, I found three areas may be related to the claim potentially:

1. Hypergraphs or family of sets: in such context, it can be paraphrased into that a multiple $x$-uniform $bx$-regular hypergraph with $abx$ hyperedges includes an $x$-uniform $x$-regular partial subhypergraph with $a$ hyperedges.
2. Block design or more generally, combinatorial design: the claim now becomes that a 1-$(a, x, bx)$ design comprises a 1-$(a, x, x)$ sub-design; the sub-design is symmetric (the number of points equals the number of blocks) and not necessarily simple (no repeated blocks allowed).
3. Algebraic graph theory: the adjacency matrix of a bipartite graph is quite unique, let alone that of a biregular one; with linear-algebraic or group-theoretic techniques, we may have a solution.

The Question

It is threefold:

1. Do there exist some pre-existed results leading to the claim?
2. Is there a better way to efficiently come up with a possible counter-example? I just wrote a Python script to randomly generate such a biregular graph and output a list of all its regular bipartite subgraphs by the brute-force search (to avoid any bias caused by heuristic algorithms). If someone is interested, I can link the script here.
3. In order to prove/disprove the claim, which other mathematical fields are the most likely to be helpful here?

Thanks in advance from a computer scientist!

Answer 1

With $x=2$ and $b \ge 1$ the claim is true.

Proof: Since $G$ has no degree-$1$ vertices, it is not a forest, so it contains at least one cycle. The cycle is your $2$-regular subgraph.

---

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

Answer 2

Here is a heuristic reason why such a claim cannot hold. I cannot make the claim rigorous as I don't know enough about random biregular bipartite graphs.

If the claim indeed holds, then for any $(x, bx)$-regular graph with $|U| = ab$, there must exist a $W \subset U$ such that $|W| = a$ and $(W, N(W) = T)$ is a $x$-regular graph.

Now consider a random $(x, bx)$-regular graph with $x = \frac{a}{2}$ and $b = 2$. My intuition says that the following holds.

1. The graph is an expander with high probability. That is $|W| < |N(W)|$ unless $|N(W)| > a / 2$. For otherwise, by assigning negative weights to $W$ and positive weights to $V - N(W)$ and $U - W$, the graph is going to have second eigenvalue $\Theta(x)$, whereas in reality, the second eigenvalue is $O(\sqrt{x})$ with high probability. This rules out the possibility of $W$ being small.

2. For any fixed $(W, T)$ with $|W| = |T|, W \subset U, T \subset V$, the degree sequence of the subgraph spanned $(W, T)$ is going to follow a normal distribution, which has PDF at most $O(\sqrt{x}^{-1})$ at any point. Thus, the probability that the subgraph is exactly $x$-regular is $$\Theta(\sqrt{x})^{-|W| -|T|}.$$ Finally, as we only need to consider $|W|, |T| \geq a/2$, this probability is at most $$\Theta(\sqrt{x})^{-a}.$$ So by the union bound over all $(W, T)$, the probability that we can find such $W, T$ is at most $$2^{|U| + |V|}\Theta(\sqrt{x})^{-a} = o(1).$$ So with high probability, such a $(W, T)$ pair does not exist.

Answer 3

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