Regular connected graph with at least one bridge.

Question

We have a connected $k$-regular graph with at least one bridge. For which $k$ does such a graph exsist?

Clearly if $k$ is even, then this graph is Eulerian so it does not have a bridge. So $k$ must be odd.

Also if we delte this bride, then we have components $A$ and $B$ with $a$ and $b$ elements, so we have for component $A$ by handshake lemma $$(a-1)\cdot k+1\cdot (k-1) = 2\alpha$$ where $\alpha $ is the number of edges in $A$. So $a$ must be odd. The same is true for $B$.

Now, I don't know how to prove that $k$ is odd is also a sufficient condition. Any idea?

Answer 1

The special case $k=1$ is uninteresting and easy. So assume $k\ge 3$.

Take a complete graph on $k+1$ vertices. Select and remove a perfect matching between $k-1$ of them (which is an even number). Each of those $k-1$ vertices now have degree $k-1$; connect them all to a fresh vertex to get their degree back up to $k$. The fresh vertex has exactly one valence left over, which will be your bridge when you connect the graph so far with a second copy of itself.

Answer 2

Your observation involving the handshake lemma can be strengthened a bit: $A$ must have degree sequence $(k, k, \ldots, k, k-1)$, where there are $a-1$ copies of $k$. A similar statement can be made for $B$. Given two graphs $A$ and $B$ with degree sequences like this, can you construct the desired $k$-regular graph? Do you know some technique for showing that such graphs exist?