0
$\begingroup$

i just started going through biconnected components can someone explain me this

Show that if G is a connected undirected graph, then no edge of G can be in two different biconnected components

$\endgroup$

1 Answer 1

1
$\begingroup$

HINT: Suppose that $G$ is connected, and $e=uv$ is an edge lying in the biconnected components $C_0$ and $C_1$, and let $C$ be the union of $C_0$ and $C_1$; show that $C$ is biconnected, contradicting the maximality of $C_0$ and $C_1$. (Recall that a biconnected component is a maximal biconnected subgraph.) It will be helpful to realize that if $H$ and $K$ are connected graphs that share a vertex, their union is also connected.

$\endgroup$

You must log in to answer this question.

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