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?

-
Do you mean the following: there exists a vertex $v$ in the tree such that $T-\{v\}$ is a disjoint union of trees such that each of these trees has at most $n/2$ vertices? – Paul Dec 4 '11 at 8:50
So if we define $f(v)$ to be the maximum size of a component after $v$ is removed, you're trying to show that there's a vertex where $f(v)$ is at most $n/2$. A good idea to try for this sort of thing is to imagine that you've already found the best possible $v$ (a $v$ for which no other vertex has a smaller value of $f$). Suppose that this "best" $v$ still gives you a component of size larger than $n/2$. Does that give you any thoughts about a choice of vertex that might be even better? – Kevin Costello Dec 4 '11 at 9:10
@Kevin: Why don't you turn your comment into an answer? – Stefan Geschke Dec 4 '11 at 9:33
Crossposted on cstheory.SE. – Raphael Dec 4 '11 at 11:19

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$.