$G = (V, E)$ is a 3-connected plane triangulation. Let $S \subset V$ such that $G(V - S)$ is disconnected. Is it true that $G(S)$ must contains a separating cycle?

My intuition is leading me to believe it is true, but I can not prove it.

MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.

Sign up to join this community
Anybody can ask a question

Anybody can answer

The best answers are voted up and rise to the top

$\begingroup$
$\endgroup$

$G = (V, E)$ is a 3-connected plane triangulation. Let $S \subset V$ such that $G(V - S)$ is disconnected. Is it true that $G(S)$ must contains a separating cycle?

My intuition is leading me to believe it is true, but I can not prove it.

$\begingroup$
$\endgroup$

Take one component $H$ of $G(V-S)$ and let $S'$ be the set of vertices in $S$ that are adjacent to a vertex in $H$. Then $S'$ is separating: it separates $H$ from the rest of $G$. Draw $G$ in the plane. There is a simple closed (Jordan) curve $C$ in the plane which intersects the drawing exactly at $S'$ (elsewhere lying in the interiors of faces) such that there are vertices in both the exterior and the exterior of $C$. Two vertices of $S'$ that are consecutive on $C$ must be connected by an edge of $G$, since all the faces of $G$ are triangles. So the vertices of $S'$ lie on a cycle given by the order they lie on $C$.

A shorter description: Take any component $H$ of $G(V-S)$ and contract it to a vertex. You still have a triangulation and now it is obvious that its neighbouring vertices form a cycle.