1
$\begingroup$

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?

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

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:

Non-biconnected non-bipartite connected regular graph.

$\endgroup$

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.