Show that if a tree is balanced than each of its partite sets contains a leaf.

Question

I am asked to show that the following holds. Show that if a tree is balanced than each of its partite sets contains a leaf.

Note balanced means that $|U| = |W| $ where $U$ and $W$ are $G$'s partite sets.

Now what i originally tried to do was use the fact that in a tree basically every vertex is a cut vertex but apparently i'm not allowed to do that because in this particular course we haven't learned what a cut vertex is yet. i should be allowed to use the concept of removing a vertex from the graph just not it being a cut vertex specifically.

i tried considering the longest path and showing that there was a leaf on each end of it but then i couldn't show that one end was in $U$ and the other was in $W$.

Any advice on how to complete this?

Answer 1

Notice that the sum of the degrees in each part is the same, since every edge crosses from one part to the other. We know that a tree with $n$ nodes has $n{-}1$ edges so the sum of the degrees in each part is also $n{-}1$, since every edge crosses from one part to the other. Then in each part we have $n/2$ nodes with degree values that sum to $n{-}1$ and by a version of the pigeonhole principle, there must be at least one vertex of degree one (a leaf) in each part.

Answer 2

Consider a proof by contradiction. Suppose that one of the partite sets (w.l.o.g, say $U$) doesn't contain a leaf. Then $d(u)\geq 2~\forall~u\in U$ which implies that $U$ contains a cycle, and hence $G$ contains a cycle. But since $G$ is a tree, it is acyclic, so we have a contradiction.

Answer 3

Suppose there is no leaf in $V$, and root the tree at a vertex in $U$. We'll count the number of pairs $(u,v)$ with $u\in U$, $v\in V$, and $u$ is a child of $v$.

Every vertex in $U$ has exactly one parent, except for the root. So the number of such pairs is $|U|-1.$ But every $v\in V$ has at least one child, since it is not a leaf. So the number of such pairs is at least $|V|>|U|-1,$ contradiction.

You can adapt this argument to show that there are always at least $|V|-|U|+1$ leaves in $V$.