Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.
Updated
Source. Section 4.13, printed p. 458 (published PDF).
Statement. Let be planted for , and let be flowered with blossom . Contracting leaves a planted tree for , with its pseudovertex outer. All other labels are unchanged.
Proof. The blossom consists of two branches from their common outer vertex , together with , as in Section 4.5. Contracting that unique circuit in the connected graph leaves a connected graph with one fewer edge than vertices, and hence a tree.
Every inner vertex of in the blossom uses its two tree edges on the circuit. It has no further tree edge leaving it. Thus a tree edge crossing the blossom boundary has an outer endpoint in and an inner endpoint outside. Marking the new vertex outer preserves alternating incidence. Inner vertices outside retain degree two.
The internal matching of covers every vertex except . If is not the root, exactly its matching edge along the stem crosses the boundary. If is the root, no matching edge crosses. The contracted restriction therefore matches every inner vertex and leaves just the original root, or the contracted root, exposed. No new matching edge meets the tree from outside, because the original tree was planted. This proves plantedness in both cases.