Definition:Complete Bipartite Graph

Definition

A complete bipartite graph is a bipartite graph $G = \left({A \mid B, E}\right)$ in which every vertex in $A$ is adjacent to every vertex in $B$.

The complete bipartite graph where $A$ has $m$ vertices and $B$ has $n$ vertices is denoted $K_{m, n}$.

Note that $K_{m, n}$ is the same as $K_{n, m}$.

Examples

Basic Properties

• $K_{1, n}$ = $K_{n, 1}$ is a tree for all $n$, and no other complete bipartite graphs are trees.

• $K_{n, n}$ is $n$-regular for all $n$, and no other complete bipartite graphs are regular.

• $K_{n, n}$ is Hamiltonian for all $n \ge 2$, from Complete Hamiltonian Bipartite Graph, and no other complete bipartite graphs are Hamiltonian.

• $K_{1, 1}$ is semi-Hamiltonian, as is $K_{n, n+1}$ for all $n \ge 2$, from Condition for Complete Bipartite Graph to be Semi-Hamiltonian, and no other complete bipartite graphs are semi-Hamiltonian.

• $K_{1, 1}$ is the complete graph $K_2$, and no other complete bipartite graphs are complete.

• $K_{1, 1}$ and $K_{1, 2}$ are the path graphs $P_2$ and $P_3$ and no other complete bipartite graphs are path graphs.

• $K_{2, 2}$ is the cycle graph $C_4$, and no other complete bipartite graphs are cycle graphs.

• $K_{1, 3}$ is known as a claw.