Let G be a planar graph with a fixed planar drawing $Γ$. A separating cycle of G is a cycle $C$ such that the curve traced by $C$ in $Γ$ has at least one vertex strictly inside and strictly outside.
Note: $uwv$ is a separating cycle .
I’d like to prove that a planar and triangulated graph is k connected if and only if it has no separating cycle of length at most k−1.
The necessary condition is obvious. I was stuck in a proof of sufficient condition. I 'd like to know the reason why we will get $G$ is $k$ connected when the triangulated planar graph $G$ has no separating cycle of length at most $k−1$.
Some definitions and theorems that may be used:
- A connected graph G is said to be k-vertex-connected (or k-connected) if it has more than k vertices and remains connected whenever fewer than k vertices are removed.
- [Menger's theorem] An equivalent definition is that a graph with at least two vertices is $k$-connected if, for every pair of its vertices, it is possible to find k vertex-independent paths connecting these vertices.
- A planar graph $G$ is called triangulated if every face is bounded by a triangle.

Suppose not, i.e. for some plane triangulation there is a separating set $S$ of size $k-1$ which does not contain a cycle.
Since $S$ is separating, we can divide the remaining vertices into two non-empty sets $T,U$ such that no edge connects $T$ to $U$. But since $S$ does not contain a cycle, the region of the plane remaining after removing $S$ and all edges spanned by $S$ is path-connected. In particular, there is a curve in the plane between a vertex in $T$ and a vertex in $U$.
Look at sequence of faces of the triangulation this curve passes through. Note that we can't move directly from a face with all vertices in $S\cup T$ to one with all vertices in $S\cup U$, since the common vertices to these faces would both be in $S$, but we never cross an edge between vertices of $S$. So the first face we encounter with a vertex in $U$ also contains some vertex in $T$. Since this face is a triangle, there is an edge between these vertices, contradiction.