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?

  • $\begingroup$ 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. $\endgroup$ – David Eppstein Apr 26 at 23:28
  • 2
    $\begingroup$ @DavidEppstein The vertices in $L$ can have degree $d$ or $d+1$ $\endgroup$ – Karagounis Z Apr 26 at 23:49
  • 1
    $\begingroup$ 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$? $\endgroup$ – Chandra Chekuri Apr 27 at 1:43
  • 2
    $\begingroup$ Yes! I want such a graph for every $d$ and $k$. $\endgroup$ – Karagounis Z Apr 27 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$

  • $\begingroup$ To check my understanding, the resulting graph has $k(d-1)$ many vertices of degree $d+1$? $\endgroup$ – Karagounis Z Apr 28 at 4:23
  • 1
    $\begingroup$ 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$. $\endgroup$ – Neal Young Apr 28 at 13:09
  • $\begingroup$ 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. $\endgroup$ – Karagounis Z Apr 29 at 3:43
  • 1
    $\begingroup$ 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). $\endgroup$ – Neal Young Apr 29 at 15:01
  • 1
    $\begingroup$ 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$ $\endgroup$ – Neal Young May 10 at 1:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.