Showing that the complete bipartite graph $K_{a,b}$ is a tree if and only if $a=1$ or $b=1$.

Question

Let $K_{a,b}$ be the complete bipartite graph. Show that $K_{a,b}$ is a tree if and only if $a = 1$ or $b = 1$.

The way my professor showed us for a complete graph is as below. I just don't know how to start for a complete bipartite graph.

$K_a$ is a tree if and only if $a=2$ or $a=1$.

Proof: For all $u\in V(K_a)$, $\deg(u) = a-1$ implies that $$2|E(K_a)| = \sum \deg(u) = (a-1)|V(K_a)|=a(a-1),$$ so $|E(K_a)|=\frac{a(a-1)}{2}.$

Since $K_a$ is connected, it is a tree if and only if \begin{eqnarray*} 0 &=&|E(K_a)| -|V(K_a)| +1 \\ &=& a(a-1)/2 -a +1 \\ &=& \frac{1}{2}(a(a-1)-2a+2)\\ &=& 1/2[a(a-1)-2(a-2)] \\ &=& 1/2[(a-1)(a-2)] =0 \end{eqnarray*}

Thus $K_a$ is a tree if and only if $a-1=0$ or $a-2=0,$ i.e., $a=1$ or $a=2$.

$K_{a,b}$ is a tree if and only if $a=1$ or $b=1$.

Proof: For all $u,v \in V(K_{a,b})$, $\deg(u) = a$ and $\deg(v) = b $ implies that $$2|E(K_{a,b})| = \sum \deg(u) + \sum \deg(v)= ab+ab=2ab,$$ so $|E(K_{a,b})|=ab.$

Since $K_{a,b}$ is connected, it is a tree if and only if \begin{eqnarray*} 0 &=&|E(K_{a,b})| -|V(K_{a,b})| +1 \\ &=& ab-a-b +1 \\ &=& (a-1)(b-1)=0\end{eqnarray*}

Thus $K_{a,b}$ is a tree if and only if $a-1=0$ or $b-1=0,$ i.e., $a=1$ or $b=1$.

Answer 1

If $a>1$ and $b>1$, then let $A=\{a_1,\dots,a_s\}$ and $B=\{b_1,\dots,b_t\}$ be the two parts of vertices with $s>1$ and $t>1$. We can then find a circuit in the graph, say $a_1b_1a_2b_2a_1$.

Answer 2

Let the first set have nodes $v_1,v_2,...v_a$ and the second set have nodes $w_1,w_2,....w_b$.

1. Now if both $a$ and $b$ are greater than one then you always find a cycle in the graph , take the minimal case $a=b=2$, then you would have a cycle $(v_1,w_1),(w_1,v_2),(v_2,w_2),(w_2,v_1)$ , here $(i,j)$ means edge between node $i$ and $j$. Thus for every case where $a>=2 , b>=2$ you will find a cycle and graph is not a tree.
2. If both $a=b=1$ it is trivial to see the graph is a tree.
3. Last case is exactly one of $a$ and $b$ is equal to one ( say $a$=1 and $b \ne 1$ ). In this case it is again it is trivial to see graph is tree, its a simple graph which is connected and number of nodes is $b+1$ and number of edges $b$ ( one less than number of nodes ) thus it is a tree.

Answer 3

Number of edges in a complete bipartite graph $K_{m,n}$ is $mn$.

Number of edges in a tree with $v$ vertices is $v-1$.

Hence, if we want $K_{a,b}$ to be a tree, we need

$$ab = a+b-1 \implies ab-a-b+1 = 0\implies (a-1)(b-1) = 0 \implies a = 1 \text{ or }b=1$$