2
$\begingroup$

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?

  • 0
    [Crossposted](http://cstheory.stackexchange.com/questions/9274/proof-about-trees) on cstheory.SE.2011-12-04

1 Answers 1

7

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

  • 0
    @Dave: NO! The whole point here is to consider edges, not vertices. I$f$ you remove a vertex, you can $g$et any number of disconnected subtrees, but if you remove an edge you get exactly two subtrees (possibly reduced to a single vertex) which is a good base for comparison. Once the edges are oriented, one starts considering vertices.2011-12-07