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
    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?2011-12-04
  • 3
    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?2011-12-04
  • 1
    @Kevin: Why don't you turn your comment into an answer?2011-12-04
  • 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
    This is an elegant version of the argument that @Kevin suggested; I like it.2011-12-04
  • 0
    @brain M. Scott: Yes Kevin C. certainly provided the inspiration. My thanks to him!2011-12-04
  • 0
    I think you meant "if one would remove the vertex" in your first sentence?2011-12-06
  • 0
    @Dave: NO! The whole point here is to consider edges, not vertices. If you remove a vertex, you can get 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