Show that in any tree there exists a node such that, if we remove this node and the edges adjacent to it, we will obtain trees which have at most n/2 nodes (the removed node is not counted anymore).
I've been thinking for a proof to that but couldn't come up with something. Any ideas?
Orient all edges towards the larger of the two subtrees obtained if one would remove the edge (if the two subtrees have equal size toss a coin). Now starting in an arbitrary node follow some edge in the oriented direction until this is no longer possible, in other words until all edges of the current node point towards it (it is obvious this terminates, because a tree has no circuits). Then it is obvious that removing all those edges and the current node cannot leave any subtree of size exceeding $n/2$.