Spanning trees with many leaves (Q5890331)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Spanning trees with many leaves |
scientific article; zbMATH DE number 1655614
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Spanning trees with many leaves |
scientific article; zbMATH DE number 1655614 |
Statements
Spanning trees with many leaves (English)
0 references
3 June 2002
0 references
spanning tree
0 references
leaves
0 references
In this paper, it is shown that for every \(t\geq 2\), and every graph \(G=(V,E)\) with \(|V|\neq t+2\) and \(|E|\geq |V|+ t(t-1)/2\), \(G\) has a spanning tree with more than \(t\) leaves. This bound is sharp. Similar results are given for the case that \(|V|=t+2\).
0 references
