Spanning trees with many leaves in cubic graphs
Jerrold R. Griggs, Daniel J. Kleitman, Aditya Shastri · Journal of Graph Theory · 1989
Abstract For a connected graph G let L(G) denote the maximum number of leaves in any spanning tree of G. We give a simple construction and a complete proof of a result of Storer that if G is a connected cubic graph on n vertices, then L(G) ⩾ [(n/4) + 2], and this is best possible for all (even) n. The main idea is to count the number of “dead leaves” as the tree is being constructed. This method of amortized analysis is used to prove the new result that if G is also 3‐connected, then L(G) ⩾ [(n/3) + (4/3)], which is best possible for many n. This bound holds more generally for any connected cubic graph that contains no subgraph K4 ‐ e. The proof is rather elaborate since several reducible configurations need to be eliminated before proceeding with the many tricky cases in the construction.