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

530 Views Asked by At

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.

1

There are 1 best solutions below

1
On

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.