Let m n Z m n greaterthanorequalto 1 Recall from Assignment

Let m, n Z, m, n greaterthanorequalto 1. Recall (from Assignment 3) that the complete bipartite graph K_m, n is the graph with set of vertices V = V_1 V_2, such that |V_1| = m and |V_2| = n, and with set of edges {{upsilon_1, upsilon_2}: upsilon_1 V_1, upsilon_2 V_2}. For which values of (m, n) is K_m, n a tree?

Solution

It is sufficient to Show that The complete bipartite graphs K1;n, known as the star graphs, are trees. Prove
that the star graphs are the only complete bipartite graphs which are trees.
Solution: Let Km;n be a complete bipartite graph such that m; n > 1. For
u1; u2; v1; v2 2 V (Km;n), let u1 and u2 be elements of the bipartition set of order
m and v1 and v2 be elements of the bipartition set of order n. By de nition of the
complete bipartite graph, there exists an edge e1 with endvertices u1 and v1, an
edge e2 with endvertices u1 and v2, an edge e3 with endvertices u2 and v1 and an
edge e4 with endvertices u2 and v2.
Therefore c = {u1; e1; v1; e3; u2; e4; v2; e2; u1}
is a walk in Km;n with distinct vertices except for the initial and nal vertex, which
are the same. That is, c is a cycle in Km;n. Hence, Km;n is not a tree.