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

December 25, 2008

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 $x_2,y_2\in E(G)$ and $y_2,x_1\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.

• Mathematics,
• Computer Science,
• Graph Theory,
• Proof