图论中blocks与cut-vertex相关定理的非subtree证明方法问询

Hey there! Let's break this down together. First, let's restate the theorem we're focusing on (from Chang's Graphs and Digraphs 4th edition) to make sure we're aligned:

Let G be a graph with one or more cut-vertices. Then, among the blocks of G, there are at least two which contain exactly one cut-vertex of G.

I get that avoiding the block tree (subtree) approach feels tricky at first, but let's try a proof by contradiction—it's a solid alternative here. Let's start by recalling quick definitions to ground us:

• A block is a maximal connected subgraph of G with no cut-vertices.
• A cut-vertex is a vertex whose removal increases the number of connected components in G.

Proof Outline (No Subtree Needed) #

Suppose the theorem is false. That means there are fewer than 2 blocks with exactly one cut-vertex—so either 0 or 1 such blocks. Let's check both cases:

1. Case 1: 0 blocks have exactly one cut-vertex
   Every block in G contains at least two cut-vertices. Pick any block B₁, and take one of its cut-vertices v₁. By definition, v₁ must belong to at least one other block B₂ (since removing v₁ disconnects G, so it's linking multiple blocks). Now, B₂ has another cut-vertex v₂ (we assumed every block has ≥2), which connects to another block B₃. Repeat this process: B₃ → v₃ → B₄ → ...

   Since G has a finite number of blocks, this sequence must eventually loop (we'll hit a block we've already visited). But this creates a cycle of blocks connected by cut-vertices—and here's the contradiction: take any cut-vertex in this cycle, say v₁. If we remove v₁, the blocks in the cycle are still connected via the other cut-vertices in the loop, so G doesn't split into more components. That directly violates the definition of a cut-vertex. So this case is impossible.

2. Case 2: Only 1 block has exactly one cut-vertex
   Let this unique block be B₀, with its single cut-vertex v₀. All other blocks have ≥2 cut-vertices. Start at v₀ and move to another block B₁ (since v₀ is a cut-vertex, it must link to at least one other block). B₁ has another cut-vertex v₁, which links to B₂, and so on. Again, since blocks are finite, we either loop back (same contradiction as Case 1—creating a cycle that breaks the cut-vertex definition) or we keep moving forever, which is impossible because there's a fixed number of blocks. Either way, this case falls apart.

Since both contradictory scenarios are impossible, the original theorem must hold: G has at least two blocks that each contain exactly one cut-vertex.

备注：内容来源于stack exchange，提问作者render_18