# Does such a bipartite graph exist?

In the course of my studies on graphs I sometimes use gadgets. I recently came upon a need for a certain bipartite graph with the following properties, and I am wondering if anyone knows if such a graph exists, or can give a construction.

Given two integers $$d$$ and $$k$$, I seek an undirected bipartite graph $$G=(L∪R,E)$$ with:

• All vertices in $$L$$ have degree either $$d$$ or $$d+1$$.
• Exactly $$k$$ vertices in $$R$$ have degree $$d−1$$, all other vertices in $$R$$ have degree exactly $$d$$
• The graph is $$d−1$$ edge-connected.

I really believe that such a graph does exist. But it is a bit difficult to come up with a proof, or a construction. Anyone can show that such a graph exists?

• Do you have any important constraints on $d$ and $k$? An obvious one is that if $d$ is even and $k$ is odd, your graph cannot exist, because it would have an odd number of odd-degree vertices. Apr 26, 2021 at 23:28
• @DavidEppstein The vertices in $L$ can have degree $d$ or $d+1$ Apr 26, 2021 at 23:49
• David's question is about $k$. If there is no constraint on $k$ then you can set $k=0$ and can construct your desired graph. Are you asking whether a graph satisfying your conditions exists for every $d$ and $k$? Apr 27, 2021 at 1:43
• Yes! I want such a graph for every $d$ and $k$. Apr 27, 2021 at 3:01

Theorem 1. For every $$d$$ and $$k$$, there is a graph with the desired properties.

I'll describe the construction in two stages.

First, construct a bipartite multi-graph $$G_1=(L_1, R_1, E_1)$$ where

• $$L_1=\{\ell_1,\ell_2,\ldots,\ell_k\}$$

• $$R_1 = \{r_1, r_2, \ldots, r_k\}$$

• $$E_1$$ is the multi-set union of $$d-1$$ matchings $$M_1, M_2, \ldots, M_{d-1}$$, where

• $$M_h = \{(\ell_i, r_j) : (i + j + h) \bmod k = 0\}$$ for $$h\in\{1,\ldots, d-1\}$$

Note that there may be multiple copies of each edge in the multigraph $$G_1$$. (In particular, in the case that $$d-1\ge k$$, we can have $$M_h = M_{h+k}$$.) We add a copy of $$(\ell_i, r_j)$$ to $$E_1$$ for each occurrence in any matching, making $$E_1$$ a multiset and $$G_1$$ a multigraph.

Lemma 1. $$G_1$$ is $$(d-1)$$-edge connected.

Proof. Consider the $$d-1$$ edge sets $$M_1 \cup M_2$$, $$M_2 \cup M_3$$, $$\ldots$$, $$M_{d-2} \cup M_{d-1}, M_{d-1} \cup M_1$$. Each such edge set is a hamiltonian cycle, so any cut is crossed by at least $$2(d-1)$$ edges in the multiset union of these $$d-1$$ edge sets. But each edge (copy) occurs twice in this multiset union, so any cut is crossed by at least $$(d-1)$$ edge (copies). $$~~\Box$$

Now obtain the desired graph $$G=(L, R, E)$$ from $$G_1$$ as follows. For each vertex $$\ell_i$$ in $$L_1$$, replace $$\ell_i$$ by a distinct copy of $$K_{d,d}$$ (the complete bipartite graph with $$d$$ vertices on each side), and replace each edge copy $$(\ell_i, r_j)$$ in $$E_1$$ by an edge from a vertex on the left side of the $$K_{d,d}$$ to $$r_j$$, so that each vertex on the left side of each $$K_{d, d}$$ has at most one edge added in this way. This is possible because each $$\ell_i$$ has degree $$d-1$$, and the $$K_{d,d}$$ that replaces it has $$d$$ vertices on its left side. Note that $$G$$ is a graph (not a multigraph), and that $$G_1$$ is obtained by contracting each $$K_{d, d}$$ into a single vertex.

Take $$L$$ to contain the vertices on the left sides of the $$K_{d, d}$$'s (each of degree $$d$$ or $$d+1$$). Take $$R$$ to contain the $$k$$ degree-$$(d-1)$$ vertices in $$R_1$$, together with all vertices on the right sides of the $$K_{d, d}$$'s (each of degree $$d$$). To finish, we prove the following lemma:

Lemma 2. $$G$$ is $$(d-1)$$-edge connected.

Proof. Suppose otherwise for contradiction. Let $$C$$ be a cut of $$G$$ with less than $$d-1$$ edges. The cut $$C$$ respects (doesn't cut) any $$K_{d, d}$$, because each $$K_{d, d}$$ is itself $$d$$-edge connected. So contracting each $$K_{d, d}$$ yields a cut in $$G_1$$ that has less than $$d-1$$ (multi) edges, contradicting Lemma 1. $$~~~\Box$$

• To check my understanding, the resulting graph has $k(d-1)$ many vertices of degree $d+1$? Apr 28, 2021 at 4:23
• Right, because there are $k$ $K_{d'd}$'s, and, in each, $d-1$ of its $d$ "right" vertices get one extra edge from some $\ell_i$. Apr 28, 2021 at 13:09
• Thank you, this is a good construction. It would be great for me if there were only $d-1$ many degree $d+1$ vertices. By any chance can your graph be modified to satisfy this? If it's not straightforward I will think on it more. Apr 29, 2021 at 3:43
• That's not possible in general. Suppose the left side has $k$ degree-$(d-1)$ vertices and some $i$ degree-$d$ vertices, while the right side has some $x$ degree-$(d+1)$ vertices and some $j$ degree-$d$ vertices. Then the number of edges must be $k(d-1) + i d = x (d+1) + j d$. Taking both sides mod $d$ gives $x\equiv -k \pmod d$ as a necessary condition. So $x=d-1$ is impossible, except maybe in the case that $1 \equiv k\pmod d$ (which doesn't hold in general). Apr 29, 2021 at 15:01
• I think $G_1$ is $r$-vertex connected (if $2\le r \le k$). Consider deleting any $r-1$ vertices from $G_1$. Assume WLOG (by symmetry) that $\ell_1$ is deleted and $\ell_2$ is not. For any non-deleted vertex $\ell_i \ge 2$, let $\ell_{i+x}$ be the next non-deleted vertex on the left. So (at least) the $x \le r-1$ vertices $\ell_1, \ell_{i+1}, \ell_{i+2}, \ldots, \ell_{i+x-1}$ have been deleted. Vertices $\ell_i$ and $\ell_{i+x}$ share $r-x$ neighbors $r_{i+x}, r_{i+x+1}, \ldots, r_{i+r-1}$, at least one of which is not deleted, so there is a 2-step path from $\ell_i$ to $\ell_{i+x}\ldots$ May 10, 2021 at 1:57