Outerplanar graphs

Task number: 4191

Prove the three-color theorem for outerplanar graphs, i.e. for graphs that have a planar drawing such that all vertices lie on the outer face.

  • Hint

    First, show the existence of a vertex of bounded degree.

  • Solution

    Without loss of generality, we can assume that the outer face is bounded by a cycle and that each inner face is a triangle – such a graph is obtained by adding edges to an outerplanar graph as long as the graph remains outerplanar.

    We now show that such an outerplanar graph contains a vertex of degree at most two: By adding a vertex to the outer face connected to all other vertices, we get a planar graph in which all faces are triangles. This graph has \( n + 1 \) vertices, \( 3n-3 \) edges, \( 2n-2 \) of triangular faces and one vertex of degree \( n \). If we remove the added vertex, \( n-2 \) of the triangular faces (and one \( n \)-gonal) will remain. Each edge on the outer face must separate this face from some triangular face. Because there are fewer triangular face than the edges on the outer face, some triangular faces have two edges in common with the outer face. These two edges define the vertex of degree two.

    (An alternative argument, more concise but more demanding on imagination: The subgraph of the dual defined by the inner faces is a tree. The leaves of this dual correspond to faces with vertices of degree two.)

    We proceed by induction, we take such a vertex, we color the rest by the induction hypothesis. The coloring can also be extended to the removed vertex, because the neighbors block at most two colors from three.

Difficulty level: Moderate task
Proving or derivation task
Cs translation
Send comment on task by email