A complete bipartite graph is a tree only if the order of one of partite sets is 1

Let G=(V,E) be a complete bipartite graph of an order at least two with partite sets X and Y. Then either |X|=1 or |Y|=1.


Assume G is a tree and |Y|>1. We prove the statement by contradiction.

Suppose |X|>1. Pick any pair of distinct vertices x1 and x2 in X, and follow any edge from x1 to some vertex y1 in Y. There must be such an edge {y1,x2}E(G) since G is a complete bipartite graph. Furthermore, there must be another vertex y2 in Y since |Y|>1. Because G is a complete bipartite graph, we have {x2,y2}E(G) and {y2,x1}E(G). Now consider a path x1y1x2y2x1, 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 |X|=1. A similar argument shows that |Y|=1 if |X|>1.