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


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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.