I'm reading Introduction to Graph Theory by Douglas West, and one of the propositions is

Two blocks in a graph share at most one vertex.

A block of a graph $G$ is a maximal connected subgraph of $G$ that has no cut-vertex.

The proof is as follows:

We use contradiction. Suppose that blocks $B_1$, $B_2$ have at least two common vertices. We show that $B_1 \cup B_2$ is a connected subgraph with no cut vertex, which contradicts the maximality of $B_1$ and $B_2$. When we delete one vertex from $B_i$, what remains is connected. Hence we retain a path in $B_i$ from every vertex that remains to every vertex of $V(B_1) \cap V(B_2)$ that remains. Since the blocks have at least two common vertices, deleting a single vertex leaves a vertex in the intersection. We retain paths from all vertices to that vertex, so $B_1 \cup B_2$ cannot be disconnected by deleting one vertex.

I'm confused as to where $B_i$ comes from in this proof. Is it different from $B_1 \cup B_2$? If so, what is it? That paragraph is the first time $B_i$ showed up in the section.

  • 5
    $\begingroup$ Bi is just shorthand for B1 or B2. $\endgroup$
    – ericf
    Sep 28 '18 at 22:23

If we can find two distinct vertices in $B_1 \cap B_2$, then the idea is that removing a vertex in the intersection maintains at least another vertex to connect $B_1$ with $B_2$, thus 2-connectivity of $B_1 \cup B_2$ (which is a larger 2-connected subgraph).


Your Answer

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