<p><strong>Theorem 1.</strong> <em>For every <span class="math-container">$d$</span> and <span class="math-container">$k$</span>, there is a graph with the desired properties.</em></p>
<p>I'll describe the construction in two stages.</p>
<p>First, construct a bipartite multi-graph <span class="math-container">$G_1=(L_1, R_1, E_1)$</span> where</p>
<ul>
<li><p><span class="math-container">$L_1=\{\ell_1,\ell_2,\ldots,\ell_k\}$</span></p>
</li>
<li><p><span class="math-container">$R_1 =  \{r_1, r_2, \ldots, r_k\}$</span></p>
</li>
<li><p><span class="math-container">$E_1$</span> is the <em>multi-set</em> union of <span class="math-container">$d-1$</span> matchings <span class="math-container">$M_1, M_2, \ldots, M_{d-1}$</span>, where</p>
</li>
<li><p><span class="math-container">$M_h = \{(\ell_i, r_j) : (i + j + h) \bmod k = 0\}$</span> for <span class="math-container">$h\in\{1,\ldots, d-1\}$</span></p>
</li>
</ul>
<p>Note that there may be multiple copies of each edge in the multigraph <span class="math-container">$G_1$</span>.  (In particular, in the case that <span class="math-container">$d-1\ge k$</span>, we can have <span class="math-container">$M_h = M_{h+k}$</span>.)  We add a copy of <span class="math-container">$(\ell_i, r_j)$</span> to <span class="math-container">$E_1$</span> for each occurrence in any matching, making <span class="math-container">$E_1$</span> a multiset and <span class="math-container">$G_1$</span> a multigraph.</p>
<p><strong>Lemma 1.</strong> <em><span class="math-container">$G_1$</span> is <span class="math-container">$(d-1)$</span>-edge connected.</em></p>
<p><em>Proof.</em> Consider the <span class="math-container">$d-1$</span> edge sets <span class="math-container">$M_1 \cup M_2$</span>, <span class="math-container">$M_2 \cup M_3$</span>, <span class="math-container">$\ldots$</span>, <span class="math-container">$M_{d-2} \cup M_{d-1}, M_{d-1} \cup M_1$</span>.  Each such edge set is a hamiltonian cycle, so any cut is crossed by at least <span class="math-container">$2(d-1)$</span> edges in the multiset union of these <span class="math-container">$d-1$</span> edge sets.  But each edge (copy) occurs twice in this multiset union, so any cut is crossed by at least <span class="math-container">$(d-1)$</span> edge (copies). <span class="math-container">$~~\Box$</span></p>
<p>Now obtain the desired graph <span class="math-container">$G=(L, R, E)$</span> from <span class="math-container">$G_1$</span> as follows.
For each vertex <span class="math-container">$\ell_i$</span> in <span class="math-container">$L_1$</span>, replace <span class="math-container">$\ell_i$</span> by a distinct copy of <span class="math-container">$K_{d,d}$</span> (the complete bipartite graph with <span class="math-container">$d$</span> vertices on each side),
and replace each edge copy <span class="math-container">$(\ell_i, r_j)$</span> in <span class="math-container">$E_1$</span> by an edge from a vertex on the left side of the <span class="math-container">$K_{d,d}$</span> to <span class="math-container">$r_j$</span>, so that each vertex on the left side of each <span class="math-container">$K_{d, d}$</span> has at most one edge added in this way.  This is possible because each <span class="math-container">$\ell_i$</span> has degree <span class="math-container">$d-1$</span>, and the <span class="math-container">$K_{d,d}$</span> that replaces it has <span class="math-container">$d$</span> vertices on its left side.  Note that <span class="math-container">$G$</span> is a graph (not a multigraph), and that <span class="math-container">$G_1$</span> is obtained by contracting each <span class="math-container">$K_{d, d}$</span> into a single vertex.</p>
<p>Take <span class="math-container">$L$</span> to contain the vertices on the left sides of the <span class="math-container">$K_{d, d}$</span>'s (each of degree <span class="math-container">$d$</span> or <span class="math-container">$d+1$</span>).  Take <span class="math-container">$R$</span> to contain the <span class="math-container">$k$</span> degree-<span class="math-container">$(d-1)$</span> vertices in <span class="math-container">$R_1$</span>, together with all vertices on the right sides of the <span class="math-container">$K_{d, d}$</span>'s (each of degree <span class="math-container">$d$</span>).  To finish, we prove the following lemma:</p>
<p><strong>Lemma 2.</strong> <em><span class="math-container">$G$</span> is <span class="math-container">$(d-1)$</span>-edge connected.</em></p>
<p><em>Proof.</em> Suppose otherwise for contradiction.  Let <span class="math-container">$C$</span> be a cut of <span class="math-container">$G$</span> with less than <span class="math-container">$d-1$</span> edges.  The cut <span class="math-container">$C$</span> respects (doesn't cut) any <span class="math-container">$K_{d, d}$</span>, because each <span class="math-container">$K_{d, d}$</span> is itself <span class="math-container">$d$</span>-edge connected.  So contracting each <span class="math-container">$K_{d, d}$</span> yields a cut in <span class="math-container">$G_1$</span> that has less than <span class="math-container">$d-1$</span> (multi) edges, contradicting Lemma 1.  <span class="math-container">$~~~\Box$</span></p>

CC BY-SA 4.0
2021-04-28T04:23:07.077Z
To check my understanding, the resulting graph has $k(d-1)$ many vertices of degree $d+1$?
Karagounis Z
CC BY-SA 4.0
2021-04-28T13:09:16.097Z
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$.
Neal Young
CC BY-SA 4.0
2021-04-29T03:43:57.387Z
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.
Karagounis Z
CC BY-SA 4.0
2021-04-29T15:01:52.110Z
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).
Neal Young
CC BY-SA 4.0
2021-05-08T05:10:15.720Z
Hi again. Your construction of $G_1$, a r-regular, r-ege-connected bipartite graph has been really useful to me. I was wondering if the same graph also r-vertex-connected?
Karagounis Z
CC BY-SA 4.0
2021-05-08T12:48:25.567Z
With $r=d-1$?  Not in general.  E.g. take the case when $k=d-1=r$.  Then $G_1$ is just $K_{k,k}$, which can be disconnected by removing the $k$ vertices on one side.  Or when $k=d=r+1$.  Then removing $k-1$ of the vertices on the left leaves just one vertex on the left, which is connected to only $k-1$ of the $k$ vertices on the right.
Neal Young
CC BY-SA 4.0
2021-05-08T21:41:45.483Z
Sorry, I want to clarify. You showed that $G_1$ is a graph on $2k$ vertices which is $r$-regular and $r$-edge connected. But I'm asking whether $G_1$ is $r$-vertex connected as well (assuming $k \geq r$). To be $r$-vertex connected, we need to show that the removal of $r-1$ vertices does not disconnect the graph. It seems you are removing $r$ vertices in your examples.
Karagounis Z
CC BY-SA 4.0
2021-05-09T13:31:17.787Z
Good point, I was mistaken (showing they are not $(r+1)$-vertex connected. I'll think about it...
Neal Young
CC BY-SA 4.0
2021-05-10T01:57:32.647Z
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$
Neal Young
CC BY-SA 4.0
2021-04-27T15:40:43.780Z
2021-04-27T15:40:43.780Z
Neal Young
<p>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.</p>
<p>Given two integers <span class="math-container">$d$</span> and <span class="math-container">$k$</span>, I seek an undirected bipartite graph <span class="math-container">$G=(L∪R,E)$</span> with:</p>
<ul>
<li>All vertices in <span class="math-container">$L$</span> have degree either <span class="math-container">$d$</span> or <span class="math-container">$d+1$</span>.</li>
<li>Exactly <span class="math-container">$k$</span> vertices in <span class="math-container">$R$</span> have degree <span class="math-container">$d−1$</span>, all other vertices in <span class="math-container">$R$</span> have degree exactly <span class="math-container">$d$</span></li>
<li>The graph is <span class="math-container">$d−1$</span> edge-connected.</li>
</ul>
<p>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?</p>

CC BY-SA 4.0
2021-04-26T23:28:32.850Z
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.
David Eppstein
CC BY-SA 4.0
2021-04-26T23:49:27.500Z
@DavidEppstein The vertices in $L$ can have degree $d$ or $d+1$
Karagounis Z
CC BY-SA 4.0
2021-04-27T01:43:15.697Z
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$?
Chandra Chekuri
CC BY-SA 4.0
2021-04-27T03:01:38.793Z
Yes! I want such a graph for every $d$ and $k$.
Karagounis Z
<graph-theory><graph-algorithms><co.combinatorics>
Does such a bipartite graph exist?
Karagounis Z
# Does such a bipartite graph exist?

(Asked by: username_0 on 2021-04-26)

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?

**Tags:** graph-theory, graph-algorithms, co.combinatorics
> **Comments:**
> **username_1**: 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.  
> **username_0**: @DavidEppstein The vertices in $L$ can have degree $d$ or $d+1$  
> **username_2**: 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$?  
> **username_0**: Yes! I want such a graph for every $d$ and $k$.  

---

## 1 answers

### Answer by username_3 on 2021-04-27. Score: 6 | Accepted answer

**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$

> **Comments:**
> **username_0**: To check my understanding, the resulting graph has $k(d-1)$ many vertices of degree $d+1$?  
> **username_3**: 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$.  
> **username_0**: 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.  
> **username_3**: 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).  
> **username_0**: Hi again. Your construction of $G_1$, a r-regular, r-ege-connected bipartite graph has been really useful to me. I was wondering if the same graph also r-vertex-connected?  
> **username_3**: With $r=d-1$?  Not in general.  E.g. take the case when $k=d-1=r$.  Then $G_1$ is just $K_{k,k}$, which can be disconnected by removing the $k$ vertices on one side.  Or when $k=d=r+1$.  Then removing $k-1$ of the vertices on the left leaves just one vertex on the left, which is connected to only $k-1$ of the $k$ vertices on the right.  
> **username_0**: Sorry, I want to clarify. You showed that $G_1$ is a graph on $2k$ vertices which is $r$-regular and $r$-edge connected. But I'm asking whether $G_1$ is $r$-vertex connected as well (assuming $k \geq r$). To be $r$-vertex connected, we need to show that the removal of $r-1$ vertices does not disconnect the graph. It seems you are removing $r$ vertices in your examples.  
> **username_3**: Good point, I was mistaken (showing they are not $(r+1)$-vertex connected. I'll think about it...  
> **username_3**: 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$  

---

