Today, I discuss some topics of graph theory because I want to establish some machinery necessary to start talking about graph colorings (which I will talk about next). For those of you who are unfamiliar with this field of study, the following definitions will help very much.

**Definition: **A *simple graph*, is comprised of a set of elements called vertices, and a set of unordered pairs of vertices such that there are no multiple edges between two vertices nor are there edges looping from a vertex to itself.

We can draw in the plane by denoting its vertices as nodes, and its edges as lines drawn between two nodes if those nodes are connected. See the graph in the Figure 1.

**Definition:** A *planar graph* is a graph that can be drawn in the plane such that no two edges cross.

**Definition:** An *outerplanar graph* is a planar graph such that no vertex is bounded by interior faces of ; that is, every vertex lies on the unbounded face of .

**Definition:** A *proper coloring* of a graph is a graph in which all of the vertices are colored some color under the condition that no two vertices that share an edge are colored the same color.

**Definition:** The *chromatic number* of a graph is the minimum number of colors needs in order to be properly colored—denoted as where is the chromatic number of .

**Definition:** A *maximal outerplanar graph* is an outerplanar graph such that the addition of one more edge to would render it no longer outerplanar.

**Definition:** A *simple polygon graph* is a drawing of a regular polygon in the plane, where its vertices are the vertices of our simple polygon graph without the restriction of angles between the edges.

**Definition:** A triangulation graph of a simple polygon graph is a polygon graph comprised entirely of triangles, or ’s or 3-cycles depending on how you want to look at it, such that there are no edge crossings.

Now, the theorem that I want to prove today is the following.

**Theorem:** A graph is a maximal outerplanar graph if and only if it is a triangulation graph of a simple polygon graph.

**Proof:**[1]

() Let be a triangulation graph of a simple polygon graph. Clearly, it is a maximal outerplanar graph, for any additional interior edge results in a edge crossing and any additional exterior edge results in bounding a vertex by interior faces.

() Let be a maximal outerplanar graph. It follows that satisfies the following conditions.

1. Every exterior edge has exactly one vertex with edges on both sides of .

2. Every interior edge has exactly two vertices with edges on both sides of , one on either side of .

3. has no cutpoints—a vertex, which, upon removal, disconnects .

For (1), suppose that the edge is on the exterior of the maximal outerplanar graph. Then that means, that any vertices that connect to the end-vertices of are one one side of –that is to say that the edges connecting the end points of to other vertices must pass through ’s interior. Now, if had no vertices with edges on both sides of , then would not be maximal. If had more than one vertex with edges on both sides of , then either there is an edge crossing, or one vertex is bounded by the interior face of another vertex. Thus, there is exactly one vertex with edges on both sides of . And, we know that this vertex has edges on both sides of for otherwise, would not be maximal. For a visual representation of this contradiction, see Figure 10.

For (2), in order for to be interior, there must be at least one vertex on either side of that has edges connecting to both end-vertices of . Then, by the same argument as above, there can only be exactly one vertex on either side of that connects to both sides of .

For (3), suppose has a cutpoint, the vertex . Then, results in disconnected components of labeled , where we label first, and then label the rest of the components in a clockwise fashion. Then, we can connect to with an edge in such a way that we would not make an internal edge of . This contradicts that is maximal, thus no such exists.

Notice that (1) and (2) illustrate that is made up of triangles that have been, informally, pasted together. Notice that (3) illustrates that the boundary of is polygon. Therefore combined, we see that is a triangulation graph of a simple polygon graph.

[1] I thought of the following proof in a less formal setting and searched to find any literature that structued the proof more formally. Thankfully, Joseph O’Rourke actually published this proof in the exact way I was thinking of it in Art Gallery Theorems and Algorithms using formal terms. As such, much credit of this proof is due to his work cited here: O’Rourke, J. Art Gallery Theorems and Algorithms. Oxford University Press, 1987.

And thus, Pete, why I’ve changed my MAT concentration from Mathematics to Physical Education.

Keep up the hard work

Coach “P”

Thanks, coach!

Pingback: Coloring Outerplanar Graphs | petemcneely

Pingback: The Power of the Four Color Theorem | petemcneely