Connectivity and minimum length

Question

Prove that a simple graph G is 2-connected if and only if for every triple (x, y, z) of distinct vertices, G has an x, z-path through y

Thanks!

Answer 1

The implication from there are $k$ vertices with degree at least $2$ to there is a path of length $k$ does not hold. For a counterexample, consider 3 triangles glued together at a common vertex. There are 7 vertices, each with degree at least 2, but the longest path is just 5 vertices long.

Instead, I would think of the problem along these lines. Let $v_1 \sim v_2 \sim \dots \sim v_m$ be a path in $G$. If $m < k$, we can delete $v_1,\dots,v_{m-1}$ from $G$ and get a connected graph. Which means that $v_m \sim w$ for some $w$ not appearing earlier in the path. So the longest path has to have length at least $k$.

If you want to use your idea, you can replace "there are $k$ vertices with degree at least $2$" with "every vertex has degree at least $k$" as in this question.

Answer 2

Never forget the contraposition!

If a longest path $P$ in $G$ has length $k-1$, then $G$ is not $k$-connected.

Proof: Let $v$ be the starting vertex of $P$. Then there is no edge joining $v$ and a vertex that's not in $P$. Hence, $deg(v)<k$. Hence, $G$ is not $k$-connected.