$\begingroup$

A graph which is not a single block has at least two leaf blocks.

According to the Intro. to Graph Theory by D. West:

• Block: A maximal connected subgraph of $G$ that has no cut-vertex.
• Leaf block: A block that contains eactly one cut-vertex of $G$.

I have not well understood this statement. Would you elaborate on this statement.

Edit: Can we say this:

The block-cutpoint graph of a connected graph is a tree where its leaves denote the blocks of $G$. Since a tree has at least two leaf blocks hence the graph has at least two leaf blocks if it is not a single block.

$\endgroup$ 4

1 Answer

$\begingroup$

Your suggestion in the edit looks sound; that is what I'd do too. (Note, as pointed out in the comments, that you'll need to assume that the graph is connected, but that is commonly considered a requirement for talking about cut vertices at all).

Of course you'll need to furnish some kind of argument (or reference) for the three claims you make:

• That the block-cutpoint graph is a tree.
• That a leaf in the block-cutpoint tree must be a block.
• That a tree that is not a point has at least two leaves.

$\endgroup$ 1

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy