One triangulation = three trees

At AofA I saw a talk by Sarah Miracle who presented joint work with Dana Randall, Amanda Streib and Prasad Tetali, showing rapid mixing, for a planar triangulation with maximum degree 6, of a natural Monte Carlo Markov Chain to uniformly generate a random partition into three trees rooted at the 3 outer vertices. This reminded us of the following elementary but striking structural property of planar triangulations.

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.