Complement of G is connected.

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

Since I derive my definiton of Diameter from shortest paths I don't worry about disconnected Graphs in this answer. Let $G$ be connected and infinite, that means its vertex set is infinite.

Now for every pair of vertices $v,w$ we have 3 cases:

1. $d(v,w)=1$

2. $1<d(v,w)<\infty$

3. $d(v,w)=\infty$

We now need to prove that in any case the shortest path between $v$ and $w$ in the complement of $G$ is at most $2$. Cases 2&3 are easy, because edge $vw$ is in the complement.

Now case 1: Two cases again:

Case 1a: there is a vertex $x\in G$, so that $vx,xw$ are not in $G$. Then both are in the complement, and the shortest path has length two.

Case 1b is clearly not possible: If $d(v,w)=1$ and $vx$ or $wx$ is in the Graph for every vertex $x$, then $G$ doesn't have a infinite diameter.

(EDIT: This answers the original question of OP: If the diameter of a graph $G$ is infinite then the diameter of its complement is ≤2)