Wiki
Wiki

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 TT be planted for MM, and let T∪{e}T\cup\{e\} be flowered with blossom BB. Contracting BB leaves a planted tree for M/BM/B, with its pseudovertex outer. All other labels are unchanged.

Proof. The blossom consists of two branches from their common outer vertex bb, together with ee, as in Section 4.5. Contracting that unique circuit in the connected graph T∪{e}T\cup\{e\} leaves a connected graph with one fewer edge than vertices, and hence a tree.

Every inner vertex of TT 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 BB and an inner endpoint outside. Marking the new vertex outer preserves alternating incidence. Inner vertices outside retain degree two.

The internal matching of BB covers every vertex except bb. If bb is not the root, exactly its matching edge along the stem crosses the boundary. If bb 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. □\square