Let be a complete bipartite graph of an order at least two with partite sets X and Y. Then either or .
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 .