A simple graph is 2-connected iff for every x,y,z in $V(G)$, $G$ has an $x$-$z$ path through $y$

1.9k Views Asked by At

This is problem 4.2.8 in introduction to graph theory by West.

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

The forward direction is easy because if it is 2 connected its connected so theres a path from $x$ to $y$ and a path from $y$ to $z$ so putting them together gives a path.

I dont see how the other direction goes except to think try to show there is a simple cycle containing x and z from the assumption. Tips would be appreciated and this is not homework its just self study.

2

There are 2 best solutions below

4
On

HINT: Suppose that $x$ is a vertex whose removal disconnects the graph; there must be vertices $y$ and $z$ that are in distinct components of $G-x$. Can there be an $x,z$ path through $y$? (I’m assuming that by path you mean simple path.)

3
On

Could the forward direction be proven by using induction? Base case: n=3, so $\delta(G) \ge 2 > n/2$, hence we can say by Dirac that G is Hamiltonian. Assume true for $3,..., n-1$. Now add a vertex $v$ to G which is adjacent to $x$ and $z$. Now we get two cycles and 3 paths between $x$ and $z$. On one of them $y$ has to be included. Or did I make this too easy?