# Show that a regular, connected bipartite graph does not have a bridge.

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) Assume to the contrary there is a bridge, $ab$ by contradiction.
2) Consider the component in the graph $G-ab$ that contains $a$.
"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$.)