Solution for Section 11.5 Question 2

2. Recall that a tree is circuit-free and connected. If both m and n are greater than one, in other words, the graph has at least two vertices in each part, then the complete bipartite graph will contain a circuit (see the first graph below). So the only complete bipartite graphs which are trees are the complete bipartite graphs Km,n in which at least one of m and/or n is equal to one (an example is the second graph below).

S11_5_2.jpg (4686 bytes)

Back to Section 11.5