In Bill Tutte's famous book Graph Theory as I Have Known It he discusses Hassler Whitney's theorem on Hamiltonian cycles in planar graphs, summarising it thus:
Any strict triangulation in which there is no separating triangle has a Hamiltonian circuit.
That is fairly clear, and to me a "separating triangle" is one which, if removed, would separate the graph.
But Tutte defines it the following way:
By a "separating triangle" of a planar map is meant a circuit of three edges that is not the boundary of a face; it has at least two faces of the map inside and at least two outside.
I don't understand this…
-
Surely a circuit of three edges circumscribes a triangle, and therefore by definition must be the boundary of a face.
-
How can a circuit of three edges have more than one face inside it? For >3 edges, that's clear, but not for 3.
And how does this way of defining a separating triangle square up with more usual definitions?
Best Answer
Let us be very careful here and make a clear distinction between an abstract graph and a planar embedding. We recapitulate the following definitions:
Def. 1: Let $\mathcal{O} \subseteq \mathbb{R}^2$ be any open set. Being linked by an arc in $\mathcal{O}$ defines an equivalence relation on $\mathcal{O}$. The corresponding equivalence classes are again open. They are the regions of $\mathcal{O}$.
Def. 2: A closed set $X \subseteq \mathbb{R}^2$ is said to separate a region $\mathcal{O}'$ of $\mathcal{O}$ if $\mathcal{O}' \setminus X$ has more than one region.
Def. 3: The frontier of a set $X \subseteq \mathbb{R}^2$ is the set $Y$ of all points $y \in \mathbb{R}^2$ such that every neighborhood of $y$ meets both $X$ and $\mathbb{R}^2 \setminus X$. Note that if $X$ is open then its frontier lies in $\mathbb{R}^2 \setminus X$.
Def. 4: A plane graph (or planar map) is a pair $(V,E)$ of finite sets with the following properties (the elements of $V$ are again called vertices, those of $E$ edges):
The abstract graph of a plane graph is called planar graph.
Def. 5: When $G$ is a plane graph, we call the regions of $\mathbb{R}^2 \setminus G$ the faces of $G$. These are open subsets of $\mathbb{R}^2$ and hence have their frontiers in $G$. Since $G$ is bounded, exactly one of its faces is unbounded. This face is the outer face of $G$. The other faces are its inner faces.
Def. 6: An embedding in the plane, or planar embedding, of an abstract graph $G$ is an isomorphism between $G$ and a plane graph $G'$.
Example: Given a plane graph $G'=(V,E)$ with $V=\{v_0,v_1,v_2\}$ and $E=\{(v_0,v_1),(v_0,v_2),(v_1,v_2)\}$. $G'$ is isomorphic to $K_3$, a complete graph on three vertices. Define $X=\mathbb{R}^2 \setminus G'$, $X$ is open in $\mathbb{R}^2$. $X$ is the union of two disjoint subsets $I=\mathbb{R}^2 \setminus (G' \cup O)$ and $O=\mathbb{R}^2 \setminus (G' \cup I)$. They are the regions of $X$ and are by definition again open in $\mathbb{R}^2$. Consider the following figure:
Now, consider the following:
Def. 7: A triangle $t$ of a planar graph $G$ is called faced if there exists a plane embedding $G'$ of $G$ such that $t$ is a face of $G'$; otherwise $t$ is called faceless.
Example: Consider the graph $G'$ given by the following figure:
The triangle given by the vertex set $\{u,v,w\}$ is obviously a faceless triangle. It is easy to see topologically as well: The interior of $\{u,v,w\}$ is not arc-connected in $\mathbb{R}^2 \setminus G'$, and hence not a single region. Notice as well that the triangle $\{u,v,w\}$ has multiple faces in its interior.
To summarize, a "circuit" is a graph in an abstract sense. The planar embedding of a circuit $G$ is a plane graph $G'$ isomorphic to $G$. The definition of a face does not exist for $G$ but for $G'$. It follows easily what he means by a "separating triangle".
References:
[1] Reinhard Diestel. Graph Theory (Graduate Texts in mathematics). 5th ed. Vol. 173. Springer, 2017.
[2] C. M. (Kieka) Mynhardt and Christopher M. van Bommel. Triangle Decompositions of Planar Graphs. 2015.