# Maximal planar graph

A maximal planar graph $G$ with at least 3 vertices is a simple finite planar graph for which we cannot add any new edge $e$ such that $G \cup e$ is still planar. Is there an easy and rigorous way to prove that such a graph is connected (between every 2 vertices there is a path)?

I know that such a graph is a plane triangulation. But I don't wish to use the fact that this means $G$ is 3-connected since it seems overkill. I also know there's an intuitive argument where I look at the "face with the disconnected components" and "add an edge within it connecting them". Is there a way to make this rigorous (using topological facts like in Diestel) or maybe a better proof?

• Erm... which "connected" are you referring to... – user21820 Mar 13 '16 at 2:39
• @user21820 I've edited the question! – Wakaka Mar 13 '16 at 2:44
• are you assuming that these are graphs with a finite number of vertices? – Charlie Mar 13 '16 at 2:46
• @Charlie: Someone and I just found the answer to my question. Consider the graph that has a vertex for each point $(x,y)$ where $x$ is rational and $y$ is an integer and an edge between adjacent points with the same $x$ coordinate. This graph is a countable graph that is embedded into a plane but is disconnected into infinitely many components! If you want a graph that has some embedding into a plane but has no proper containing graph with a planar embedding, I think using reals instead of rationals, and then Zorn's lemma, but I'm unable to get it. – user21820 Mar 13 '16 at 10:12
• @Charlie: A fairly intuitive example is to start with the planar graph consisting of the edges of a tiling of the plane by equilateral triangles. Take the origin as one of the vertices. Now shrink radially by (for instance) the map $r\mapsto\tan^{-1}r$; the result is a $6$-regular maximal planar graph $G$ on countably infinitely many vertices contained within the circle of radius $\pi/2$ centred at the origin. No vertex of $G$ is accessible from outside that circle, so the union of countably infinitely many pairwise disjoint copies of $G$ is maximal planar but with cnt. inf. many components. – Brian M. Scott Mar 14 '16 at 9:51

Suppose towards a contradiction that each $G$ is a disconnected but maximal simple finite planar graph with components $G_1$ and $G_2$ for simplicity. Since $G$ is maximal, each $G_i$ must also be maximal.
We fix a specific planar embedding of $G$. First, pick any planar embedding of $G_1$ and call its image $G_1'$. The boundary edges of $G_1'$ form a simple closed curve since $G_1$ is maximal, so they divide the plane into two regions, one of which is unbounded. Call this region $O_1$. Now pick a planar embedding of $G_2$ into $O_1$, and let $G'_2$ denote the image. Define $O_2$ similarly to $O_1$ and note that $G_1' \subset 0_2$ and $G_2' \subset O_2$.
Now since $G$ is finite, $O_1 \cap O_2$ must be path connected as each $O_i$ is $\mathbb{R}^2$ with a compact set removed. The closure of $O_1 \cap O_2$ contains a vertex $v_i$ of $G_i'$ by construction, and there is a path $e$ from $v_1$ to $v_2$. Adding this path as an edge to $G'$ yields a planar graph, contradicting the maximality of $G$.
• Thanks! But what if $O_2$ lies inside one of the triangles of $O_1$? Then $O_1 \cap O_2$ might not be path connected in $G'$? (diagram) – Wakaka Mar 13 '16 at 20:00