Prove that the graph obtained by removing all 3 vertices on the outer face of a triangulating planar graph is connected.

88 Views Asked by At

Let $G$ be a triangulating planar graph with the outside face $v_1v_2v_3$. The fact seems true that $G'=G-\{v_1, v_2, v_3\}$ is connected.

Some of the starting points for my thinking: We know that any triangulating planar graph graph is 3-connected. If $G'$ is not connected, then $\{v_1, v_2, v_3\}$ is a minimal vertex cut , and any two connected components of $G'=G-\{v_1, v_2, v_3\}$ have edges adjacent to any one of $\{v_1,v_2,v_3\}$ ... And then try to derive the contradiction.

I do not know how quickly to explain this fact.

enter image description here

1

There are 1 best solutions below

1
On BEST ANSWER

Assume to the contrary that $G-\{v_1, v_2, v_3\}$ is disconnected and consider a vertex of the triangle, say, $v_1$. Consider its neighbors in clockwise order. Going clockwise, at some point we must move from a vertex $u$ in one connected component (call it $C_1$) of $G-\{v_1, v_2, v_3\}$ to a vertex $w$ in another component (call it $C_2$).

But since $G$ is a triangulation and the two neighbors $u$ and $w$ are clockwise-consecutive neighbors of $v_1$, we must have that $u$ and $w$ are adjacent (i.e., we have that $u, v_1, w$ induces a triangle). This contradicts the fact that $C_1$ and $C_2$ are different components of $G-\{v_1, v_2, v_3\}$.

NOTE: You can remove any face without disconnecting even a 3-connected plane graph that is NOT a triangulation (use Menger's Theorem cleverly).