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 \cup 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?
Best Answer
For $k=0$, we just want a $(d-1)$-edge-connected, $d$-regular bipartite graph with at least $k(d-1)$ vertices on each side. Then, add $k$ vertices to $R$, connecting each one to $d-1$ vertices in $L$, without using the same vertex of $L$ twice. By the expansion lemma, this preserves $(d-1)$-edge-connectivity.
If we don't mind having lots of vertices, then there are many ways to construct such a graph. A quick way to do it is to take an edge-disjoint union of $\lfloor \frac d2\rfloor$ Hamiltonian cycles, and then add an arbitrary perfect matching if $d$ is odd. Then there are $2 \lfloor \frac d2\rfloor \ge d-1$ edge-disjoint paths between any two vertices: $2$ from each cycle.
The $k=0$ graph is actually $d$-edge-connected for even $d$. If we want the same for odd $d$, we have to take a bit more care with the perfect matching. For example, suppose $|L|=|R|=n$ is odd; then a $3$-regular, $3$-edge-connected bipartite graph is obtained from $C_{2n}$ by joining opposite vertices. Then we can add edge-disjoint Hamiltonian cycles to that as before. Of course, for $k>0$, we will lose $d$-edge-connectivity once we add the first vertex of degree $d-1$.