Does such a bipartite graph exist?

Question

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?

Answer 1

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$