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

Let $G=\left(V,E\right)$ 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 $\left\{{y}_{1},{x}_{2}\right\}\in E\left(G\right)$ 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 $\left\{x2,y2\right\}\in E\left(G\right)$ and $\left\{y2,x1\right\}\in E\left(G\right)$. 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.