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

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!

• For fixed $a,b$, replacing $x$ with $a-x$ can be achieved via complementing the graphs. Hence, without loss of generality, one can assume $x \leq a/2$. Feb 18 at 21:16

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.

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.

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