1
$\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$
  • 1
    $\begingroup$ What is a "block"? $\endgroup$ – Henning Makholm Mar 24 at 10:39
  • $\begingroup$ @HenningMakholm I just edited the question. $\endgroup$ – Amin Mar 24 at 10:44
  • $\begingroup$ Sorry, if you take 2 disjoint $K_3$ as your graph $G$, then $G$ is not a single block but neither of the 2 $K_3$ are leaf blocks? $\endgroup$ – user 42493 Mar 24 at 10:56
  • $\begingroup$ @user42493: we assume it is connected. $\endgroup$ – Amin Mar 24 at 11:22
1
$\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$
  • $\begingroup$ I see. Thanks @HenningMakholm. $\endgroup$ – Amin Mar 24 at 11:19

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.