Question

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

Answer 1

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.

Answer 2

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.