# 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$$.

## Proof

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

Suppose $$|X|>1$$. Pick any pair of distinct vertices $${x}_{1}$$ and $${x}_{2}$$ in X, and follow any edge from $${x}_{1}$$ to some vertex $${y}_{1}$$ in Y. There must be such an edge $$\{{y}_{1},{x}_{2}\}\in E(G)$$ since G is a complete bipartite graph. Furthermore, there must be another vertex $${y}_{2}$$ in Y since $$|Y|>1$$. Because G is a complete bipartite graph, we have $$\{x2,y2\}\in E(G)$$ and $$\{y2,x1\}\in E(G)$$. Now consider a path $${x}_{1}{y}_{1}{x}_{2}{y}_{2}{x}_{1}$$, 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$$.

Q.E.D.