Complete Bipartite Graph

graph-theory

Definition

Complete Bipartite Graph

A complete bipartite graph $K_{n,m}$ is a bipartite graph where the vertex set $V$ is partitioned into two disjoint sets $V_1$ and $V_2$ such that $|V_1|=n$ and $|V_2|=m$, and every vertex in $V_1$ is connected by an edge to every vertex in $V_2$.

Special Cases

• Star Graph: The complete bipartite graph $K_{1,k}$ is known as a star graph.
• Bipartite Graphs: Any bipartite graph is a subgraph of some complete bipartite graph.