I need to show, that a connected regular bipartite graph (degree of the graph is $>1$) does not have a bridge.

Well let's assume that there is a bridge $e$. After we cut it, the graph is divided into two parts $A$ and $B$. Both $A$ and $B$ are bipartite, therefore $A=A_1 \cup A_2$, where $A_1$ and $A_2$ are independent sets. Let $a \in A_1$ be the vertex, from which we deleted one edge (the bridge). Let's consider all other edges in $A_1$. If $A_1$ has to be non-empty, because the two neighbours of $a_1$ connect to something other than $a_1$. Let $|A_1|=m$. If we consider the vertices other than $a_1$ then each of them has degree $d$ and because the regular $d$ graph fullfills Hall condition each of the other vertices in $A_1$ has a neighbour we can connect with it uniquely. Therefore $|A_2| \geq |A_1 \backslash a_1|$. And therein lies the contradiction, because $d*(m-1)+(d-1)$ edges enter $A_2$, and $|A_2|$ has at least $(m-1)$ vertices, each with degree $d$ we need an extra one with degree $d-1$., but there's only one other vertex in $G$ with degree $d-1$ and it lies in a different component, contradiction.

Is this in any way, shape or form correct?


1 Answer 1


It seems to me the general idea is there. (See if I have correctly identified your key points below)

1) Assume to the contrary there is a bridge, $ab$ by contradiction.
2) Consider the component in the graph $G-ab$ that contains $a$.
3) Count the degree sums of the two partite sets in the component and obtain the contradiction since they don't match up.

I don't think you need to invoke Hall's condition or matchings. Some of the phrasing can be brushed up a little too. For example,

"Let's consider all other edges in $A_1$.": I think you meant all edges incident to vertices in $A_1$ ($A_1$ is an independent set so there are no edges in $A_1$.)

  • $\begingroup$ Thank you :) I was afraid I was missing something. $\endgroup$ Feb 7, 2014 at 15:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .