###
Steklov Institute of Mathematics at St.Petersburg

#
PREPRINT 04/2007

H.÷. çÒÁ×ÉÎ ##
ðïóôòïåîéå ïóôï÷îïçï äåòå÷á ó âïìøûéí ëïìéþåóô÷ïí ìéóôøå÷

This preprint was accepted March 9, 2007

ABSTRACT:
We prove the following theorem: every connected graph with $k$
vertices of degree at least 4 and $m$ vertices of degree
3 has a spanning tree with at least $\lceil\frac{2}{5} \cdot k + \frac{2}{15} \cdot m\rceil$
leaves.

[Full text:
(.ps.gz)]

Back to all preprints

Back to the Steklov
Institute of Mathematics at St.Petersburg