1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Erm... which "connected" are you referring to... $\endgroup$ – user21820 Mar 13 '16 at 2:39
  • $\begingroup$ @user21820 I've edited the question! $\endgroup$ – Wakaka Mar 13 '16 at 2:44
  • 1
    $\begingroup$ are you assuming that these are graphs with a finite number of vertices? $\endgroup$ – Charlie Mar 13 '16 at 2:46
  • 1
    $\begingroup$ @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. $\endgroup$ – user21820 Mar 13 '16 at 10:12
  • 1
    $\begingroup$ @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. $\endgroup$ – Brian M. Scott Mar 14 '16 at 9:51
1
$\begingroup$

I think it is easy to make your intuitive argument precise.

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

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – Wakaka Mar 13 '16 at 20:00
  • $\begingroup$ Good catch. But notice that since your graph is disconnected, you can choose your embedding so that this doesn't happen. I'll elaborate in my response. $\endgroup$ – Charlie Mar 13 '16 at 21:10

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.