
6.7. REALIZER METHOD 213
1. In each spanning tree, the edges of G are directed from children to parent.
2. The sinks (roots) of the spanning trees are the three external vertices of G.
3. Each internal edge of G is contained in one spanning tree.
4. Each external edge of G is contained in two spanning trees and it has different
directions in the two trees.
5. Consider the edges of G with the directions they have in the three spanning trees
(the external edges are considered twice):
(a) Each non-sink vertex v of G has exactly three outgoing edges; the circular
order of the outgoing edges around v induces a circular order of the spanning
trees around v