1
$\begingroup$

enter image description here

For a graph with 3 blocks like $B_1, B_2, B_3$ if every two of them are common in a vertex like $v,u,w$ then non of these vertices are cut-vertex. Because $G-\{v\}$ is still a connected graph. Am I right?

$\endgroup$
1
  • 1
    $\begingroup$ I don't think it is possible to have such 3 blocks, because if you define block to be the maximal biconnected subgraph of $G$, then if the above is satisfied, then $B_1\cup B_2 \cup B_3$ will be a larger biconnected subgraph, hence $B_i$ are not blocks. $\endgroup$
    – MDude
    Nov 25 at 9:10
0
$\begingroup$

Let $B_1$, $B_2$ and $B_3$ be distinct pairwise-intersecting blocks.

Let $u \in B_1 \cap B_2$, $v \in B_2 \cap B_3$ and $w \in B_1 \cap B_3$. Let $P_1$ be a path in $B_1$ from $w$ to $u$, $P_2$ be a path in $B_2$ from $u$ to $v$ and $P_3$ be a path in $B_3$ from $v$ to $w$. These three paths are edge-disjoint by $(a)$ and node-disjoint (that is they do not have common inner nodes) by $(b)$. Thus if $u$, $v$ and $w$ are distinct, the concatenation of $P_1$, $P_2$, $P_3$ is a circuit containing $u$, $v$ and $w$, from which we get that $w \in B_2$, contradicting $(b)$. Hence $u = v = w$.

So it is not that $u$, $v$ and $w$ are not cut-vertices, but instead that they are the same cut-vertex.

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