连通性与最短路径：求证简单图G是2-连通的充要条件

Alright, let's work through this equivalence proof step by step, leaning on core connectivity and vertex-disjoint path concepts. We'll split this into two logical directions: necessity (if $G$ is 2-connected, the path condition holds) and sufficiency (if the path condition holds, $G$ is 2-connected).

Necessity: 2-Connected $\implies$ Path Condition Holds #

Suppose $G$ is a 2-connected simple graph. A key result from graph theory (Whitney's Theorem) tells us that 2-connected graphs have the property: any pair of distinct vertices has at least two internally vertex-disjoint paths between them. Let's take any three distinct vertices $x, y, z$.

We have two cases to cover:

1. Case 1: $y$ lies on one of the internally disjoint $x,z$-paths
   If $y$ is on either of the two vertex-disjoint $x,z$-paths (say path $P$), then $P$ itself is exactly the $x,z$-path we need—it passes through $y$ by definition. That's straightforward.

2. Case 2: $y$ is not on either of the two internally disjoint $x,z$-paths
   Let $P$ and $Q$ be the two internally disjoint $x,z$-paths. Together, $P \cup Q$ forms a cycle that includes both $x$ and $z$. Since $G$ is 2-connected, $y$ can't have only one neighbor in this cycle—if it did, that neighbor would be a cut point (removing it would disconnect $y$ from the cycle, violating 2-connectivity). So $y$ has at least two distinct neighbors $u$ and $v$ in $P \cup Q$, where $u$ sits on $P$ and $v$ sits on $Q$ (on opposite segments of the cycle between $x$ and $z$).

   We can build our desired path like this: take the subpath of $P$ from $x$ to $u$, follow the edge $u \to y$, then take the subpath of $Q$ from $v$ to $z$, connecting $y$ to $v$ via edge $y \to v$. This gives a valid simple $x,z$-path that passes through $y$.

In both cases, we've verified the path condition holds for any distinct $x,y,z$.

Sufficiency: Path Condition Holds $\implies$ $G$ is 2-Connected #

To prove $G$ is 2-connected, we need to show it has no cut vertices (and since we're dealing with three distinct vertices, $G$ has at least 3 vertices—another prerequisite for 2-connectivity).

Let's assume for contradiction that $G$ has a cut vertex $v$. Removing $v$ splits $G$ into at least two non-empty connected components, say $U$ and $W$. Now pick:

• $x \in U$, $x \neq v$
• $z \in U$, $z \neq x, v$
• $y \in W$, $y \neq v$

By the given path condition, there must be a simple $x,z$-path that passes through $y$. But here's the problem: to get from $x$ (in $U$) to $y$ (in $W$), the path has to go through $v$ (since $U$ and $W$ are disconnected in $G-v$). Then, to get from $y$ back to $z$ (also in $U$), the path would have to go through $v$ again. This creates a repeated vertex $v$ in the path, which violates the definition of a simple path (no repeated vertices allowed in simple graphs).

This contradiction means our initial assumption (that $G$ has a cut vertex) is false. Therefore, $G$ has no cut vertices, so it is 2-connected.

内容的提问来源于stack exchange，提问作者user529756