0
$\begingroup$

Show that each connected graph that is not a block has at least $2$ blocks, each containing exactly one cut-vertex.

I know:

A block of graph $G$ is the maximal connected sub-graph of $G$ that has no cut-vertices.

So "connected graph that is not a block" means that graph has cut-vertices.

What can I say now?

$\endgroup$

1 Answer 1

1
$\begingroup$

Given a graph $G$, we can associate to it a tree $T_G$, sometimes called its block-cut tree, in the following way: the vertex set of $T_G$ consists of one vertex for each block of $G$, as well as one vertex for each cut-vertex in $G$, and for each cut-vertex $v$ of $G$, we connect the vertex in $T_G$ corresponding to $v$ to the vertices corresponding to blocks containing $v$.

One can show that, as the naming suggests, $T_G$ is indeed a tree. A block that contains exactly one cut-vertex corresponds to a vertex of degree one in $T_G$; thus, your problem amounts to showing that $T_G$ has at least two leaves. This is clearly true under the assumption that $G$ itself was not $2$-connected (so that $T_G$ has at least two vertices).

$\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.