Skip to main content

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 x1 and x2 in X, and follow any edge from x1 to some vertex y1 in Y. There must be such an edge y1,x2E(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,y2E(G) and y2,x1E(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.

Q.E.D.