prove that for every tree with the maximum degree of a vertex which is S we have at least S leaves

Question

anonymous · Answer

A proof by contradiction might be the way to go here. Assume there are less than $S$ leaves. It's been a while since my GT days, but I think you should be able to establish that this assumption guarantees at least one occurrence of a cycle within the graph, and thus it is not a tree.

anonymous · Answer

Not a formal proof by any means, but one way to think about it. The simplest graph to consider would probably be the star graph on $n$ vertices. If it's assumed that $S<n$, then the only way to "delete" the leaves is to connect two together, which would give you $S=n$ with $n-2$ leaves.
|dw:1414473435992:dw|