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?


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$ – Arek Krawczyk Feb 7 '14 at 15:56

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.