Lemma 4.49.3. (Confluence and finite forests). Every sequence of elementary pruning terminates. Any sequence continued until no deletable vertex remains has the same labelled terminal graph, up to an incidence isomorphism fixing its retained vertices and its labelled legs.
Suppose is a subset of the unprotected vertices such that each connected component of the induced subgraph on is a tree, all its vertices belong to , and where counts edges from to its complement and counts its marked legs. Contracting each such tree, transferring its possible mark in the one-ended case and joining its two ends in the two-ended case, is a sequence of elementary prunings. In particular it does not change the terminal graph.
Proof
Proof. Every pruning removes one vertex and retains the nonempty set , so a sequence is finite. We verify a local commutation property. If two distinct deletable vertices are not adjacent, their operations commute. Their incident edges are disjoint; even when they have a common neighbour, the transferred labelled legs and the replacement edges give the same result in either order. Each vertex remains deletable after the other operation.
Suppose instead that the two vertices are adjacent. They have only one edge between them. Two parallel edges would exhaust both degrees, making them the whole connected graph, contrary to the existence of a protected vertex. For the same reason they cannot both have degree one. If one is a leaf and the other has degree two, deleting the leaf leaves a leaf with at most one marked leg at the second vertex. Deleting the second vertex first joins the original leaf directly to the remaining neighbour. Both orders remove the pair and transfer the same possible leg to that neighbour. If both vertices have degree two, neither has a mark, and both orders suppress the same two-vertex path. Their other neighbours may coincide: both orders then give the same loop at that common neighbour. In all cases both second deletions remain permissible and the results agree.
Induct on the number of vertices to prove confluence. For two terminal sequences with the same first deletion, apply induction to the smaller graph. For different first deletions, the preceding commutation property gives a common graph after two deletions. Induction applied to each of the two one-deletion graphs identifies its terminal graph with the terminal graph of this common graph. Thus the two original terminal graphs agree. This also proves that their retained labels and transferred marked-leg labels agree.
For the forest assertion, each has , because the whole graph is connected and its complement contains . A one-vertex tree is immediately deletable. If has more than one vertex, it has at least two leaves: take the two ends of a longest simple path. Since its total number of external ends and marks is at most two, some leaf carries at most one of these external ends or marks. Its one internal edge therefore gives . Delete it. If it carries an external edge, that edge is joined to its internal neighbour; if it carries a mark, that mark is transferred to that neighbour. The remaining tree has the same external ends and marked legs, and its vertices still belong to . Continue until the tree disappears. Its final operation is exactly the prescribed one-ended or two-ended contraction, including a loop when the two external ends have the same neighbour. Different connected components of have no edge between them, so this procedure applies to all of them. Confluence proves the last assertion. ◻