Assume G is a tree and .
We prove the statement by contradiction.
Suppose .
Pick any pair of distinct vertices and in X, and
follow any edge from to some vertex in Y.
There must be such an edge since G is a complete bipartite graph.
Furthermore, there must be another vertex in Y since .
Because G is a complete bipartite graph, we have and .
Now consider a path , which is a cycle.
But G is a tree so G is acyclic and this is a contradiction.
Thus our supposition must be false and .
A similar argument shows that if .