**Theorem**
The internal edges of a planar triangulation can be partitioned into three trees that span all inner vertices and are rooted respectively at each of the three vertices incident to the outer face.

The proof is elementary and algorithmic, by induction on the number of vertices.

Algorithm

If G is a single triangle,

Then we are done.

Else

Find an edge {u,v} with u on the outer boundary, v internal, and exactly two paths of length 2 from u to v.

Contract edge {u,v} into a vertex u', creating a contracted graph G'.

Recursively solve the problem for G', obtaining three trees, blue, white and red, where, say, the blue tree is rooted at u'.

Uncontract edge {u,v}, color it blue; other edges inherit the color of the corresponding edge of G'.

Analysis

The only question is: does there always exist an edge {u,v} with the specified properties? The answer is elementary: For u, pick any of the three outer vertices. Let u1,u2,…,uk be the neighbors of u (u2 and uk are the other two outer vertices), and consider the cycle u1-u2-…-uk-u1. Any planar cycle on k vertices has at least two "ears" (vertices from which no chords originate), and only one of them can be u2 or uk, so for v we simply take the other ear.

## No comments:

## Post a Comment

Note: Only a member of this blog may post a comment.