Question

Which complete bipartite graphs \({{\bf{K}}_{{\bf{m,n}}}}\), where \({\bf{m}}\) and \({\bf{n}}\) are positive integers, are trees?

Short answer

\({K_{1,n}}\) and \({K_{m,1}}\) are trees for all positive integers \(m\) and \(n\).

Step-by-step solution

Definition

A tree is an undirected graph that is connected and that does not contain any simple circuits.

A complete bipartite graph \({K_{m,n}}\) with a set \(M\) of \(m\) vertices and another set \(N\) with n vertices, while there are edges between every vertex in \(M\) and every vertex of \(N\).

A simple path is a path that does not contain the same edge more than once.

A circuit is a path that begins and ends in the same vertex.

Step 2: \({{\bf{K}}_{{\bf{m,n}}}}\) is connected to an undirected graph

If \(n \ge 2\) and \(m \ge 2\), there exists vertices \({m_1} \in M\), \({m_2} \in M\), \({n_1} \in N\) and \({n_2} \in N\)

Since a vertex in \(M\) is always connected to a vertex in \(N,{m_1},{m_2},{n_1},{n_{_2}},{m_1}\) forms a simple circuit and thus \({K_{m,n}}\) is not a tree when \(n \ge 2\) and \(m \ge 2\).

If \(n = 1\) and/or \(m = 1\), then \({K_{m,n}}\) cannot contain any simple circuits (as there are only edges from 1 vertex to all other vertices). Moreover, \({K_{m,n}}\) is always a connected undirected graph and thus \({K_{m,n}}\) is a true if \(n = 1\) and/or \(m = 1\).

In other words, \({K_{1,n}}\) and \({K_{m,1}}\) are trees for all positive integers \(m\) and \(n\).