# Connected, regular, bipartite graph and biconnected component

I'm learning for an exam and I can't solve this problem:

Prove that every undirected, connected, regular, bipartite graph has only one biconnected component. Give an example which shows that assumption of bipartition is necessary.

Can anyone help?

• Suppose two biconnected components are connected by some single edge. Now consider the number of neighbours of each vertex in the first component. – András Salamon Jun 14 '13 at 20:05

If the degree $d=1$, then it's not true for $K_2$. Otherwise the graph is disconnected. Now assume $d \geq 2$.

If there is a bipartite graph with $\geq 2$ biconnected components then there is a bridge $e$. If we delete $e$, then we separate the graph into two disjoint components. Take one of these components and call it $G$.

We know $G$ is a bipartite graph, so call the distinct parts $V_1$ and $V_2$, and assume the edge $e$ has an endpoint in $V_2$.

In $G$:

• The number of edges coming out of $V_1$ into $V_2$ is $dv_1$ where $v_1=|V_1|$.

• The number of edges going into $V_2$ from $V_1$ is $d(v_2-1)+(d-1)$, since one vertex in $V_2$ was an endpoint of $e$ in the original graph, but $e$ has now been deleted.

Hence $dv_1=d(v_2-1)+(d-1)$ has an integer solution, implying $0 \equiv -1 \pmod d$, giving a contradiction (since $d \geq 2$).

Without the bipartite condition, we can find non-biconnected non-bipartite connected regular graph, such as the following: