Basic Properties of Complete Bipartite Graph

Theorem

Let $G = \struct {A \mid B, E} =: K_{m, n}$ be the complete bipartite graph with $m$ vertices in $A$ and $n$ vertices in $B$.

Then $G$ has the following properties:

Indices of Complete Bipartite Graph Commute

$K_{m, n}$ is isomorphic to $K_{n, m}$

for all $m, n \in \N$.

Condition for Complete Bipartite Graph to be Edgeless

$K_{m, n}$ is edgeless if and only if either $m = 0$ or $n = 0$.

Null Graph is Complete Bipartite Graph

The null graph $N_0$ is the complete bipartite graph $K_{0, 0}$.

Complete Bipartite Graphs which are Trees

$K_{0, 0}$ is a tree

$K_{1, n}$ and $K_{n, 1}$ is a tree for all $n$

and no other complete bipartite graphs are trees.

Complete Bipartite Graphs which are Regular

$K_{n, n}$ is $n$-regular for all $n$

$K_{n, 0}$ and $K_{0, n}$ are $0$-regular for all $n$

and no other complete bipartite graphs are regular.

Complete Hamiltonian Bipartite Graph

$K_{m, n}$ is Hamiltonian if and only if $m = n > 1$.

Condition for Complete Bipartite Graph to be Semi-Hamiltonian

$K_{m, n}$ is semi-Hamiltonian if and only if either:

$m = n = 1$

or:

$m = n + 1$ (or $n = m + 1$).

Complete Bipartite Graphs which are Complete Graphs

$K_{0, 0}$ is the complete graph $K_0$

$K_{0, 1}$ and $K_{1, 0}$ are the complete graph $K_1$

$K_{1, 1}$ is the complete graph $K_2$

and no other complete bipartite graphs are complete.

Complete Bipartite Graphs which are Path Graphs

$K_{0, 0}$ is the path graph $P_0$

$K_{0, 1}$ and $K_{1, 0}$ are the path graph $P_1$

$K_{1, 1}$ is the path graph $P_2$

$K_{1, 2}$ and $K_{2, 1}$ are the path graphs $P_3$

and no other complete bipartite graphs are path graphs.

Complete Bipartite Graphs which are Cycle Graphs

$K_{2, 2}$ is the cycle graph $C_4$

and no other complete bipartite graphs are cycle graphs.