8

Part of 2017 239 Open Mathematical Olympiad

Problems(1)

finding an spanning tree with many leaves when degrees are at least 3

Source: 239 2001 S8

Assume that the connected graph

G

n

vertices all with degree at least three. Prove that there exists a spanning tree of

G

\frac{2}{9}n

graph theorycombinatoricsspanning tree