# Graph Theory: proof about the number of vertices in a Tree's component

I'm having some problem understanding the question below:

Let T = (V,E) be a tree. Show that T has a vertex v such that for all e that exists in E, the component of T-e containing v has at least |v|/2 vertices (where |v| = number of vertices, and |v|/2 is rounded up if |v| is odd). Prove that either v is unique or there are 2 adjacent vertices.

What I had interpreted initially was that there exists a vertex v such that if you take that vertex and all of its adjacent vertices to create a component, it would have at least |v|/2 vertices (upper-ceiling). (e.g., there would be at least one vertex in the Tree with degree of (|v|/2)-1 or greater). That is probably a wrong interpretation since the tree below doesn't have vertex with degree (upper-ceiling) |v|/2-1 or greater.

Could someone try to clarify the initial statement for me and help me get started on the proof? Thanks so much!

• Consider the third vertex in the chain that you've drawn. If you remove any one edge, breaking the chain into two chains, the piece containing that third vertex will contain at least three vertices. The same holds for the fourth vertex, but not for the first two or last two. It's easy to see that if a chain has $2n+1$ vertices, the middle vertex is the only one with the desired property: remove any edge, and its component has at least $n+1$ vertices. Moreover, no other vertex has that property. In a chain with $2n$ vertices, the middle two work, as in your example. The theorem says that ... Commented Feb 20, 2015 at 11:38
• ... all trees behave this way, not just chains. Commented Feb 20, 2015 at 11:39
• That's much more clear now, thanks so much! Commented Feb 20, 2015 at 15:08

## 1 Answer

I understand it to mean that there is a vertex in the "middle" of the tree, so that no matter which edge you remove (breaking it into 2 sub-trees), the sub-tree that contains that vertex is always at least half the size of the original tree.

• Thanks for the re-wording - that makes a lot more sense now. Commented Feb 20, 2015 at 15:09