Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
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? –  Kevin Costello Dec 4 '11 at 9:10
1  
@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
add comment

1 Answer 1

up vote 7 down vote accepted

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

share|improve this answer
    
This is an elegant version of the argument that @Kevin suggested; I like it. –  Brian M. Scott Dec 4 '11 at 11:26
    
@brain M. Scott: Yes Kevin C. certainly provided the inspiration. My thanks to him! –  Marc van Leeuwen Dec 4 '11 at 11:39
    
I think you meant "if one would remove the vertex" in your first sentence? –  Dave Dec 6 '11 at 20:21
    
@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. –  Marc van Leeuwen Dec 7 '11 at 7:47
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.