So I wanted to proof the following: Suppose we have a tree : T=(E,V), then for all nonempty subsets $S \subset V$ of vertices the number of edges with both endpoints in S is less or equal to $|S|-1$.
Proof:
Suppose we have a tree T=(E,V) and consider a nonempty subset $S\subset V$. We have 3 cases:
- If S=V, then the statement is trivial since T is a tree.
- If we take S such that all vertices in S are connected by some edge between then every pair of vertices is exactly connected by one edge. Since we are connected this means this actually a subtree of T and we have $|S|-1$ edges. If it was more than we would have a cycle in our tree T itself and that is not possible.
- If we take S randomly, by randomly I mean that the pairs should not be connected necessarily, then every pair in S which is connected has exactly 1 edge between them and the ones which are not connected will have no edges. Since every pair in S is not connected this is strictly less than $|S|-1$.
Is my proof correct? I think that the third case should be explained in a better way? Any tips or advice please