Complete Bipartite Graph — Definition, Formula & Examples

A complete bipartite graph is a graph whose vertices are split into two disjoint groups such that every vertex in one group is connected by an edge to every vertex in the other group, with no edges between vertices in the same group.

A complete bipartite graph $K_{m,n}$ is a bipartite graph with vertex partition $V = V_1 \cup V_2$ , where $|V_1| = m$ and $|V_2| = n$ , such that $\{u, v\}$ is an edge if and only if $u \in V_1$ and $v \in V_2$ . Equivalently, it is the bipartite graph that contains every possible edge between the two parts.

Key Formula

|E(K_{m,n})| = m \cdot n

Where:

$m$ = Number of vertices in the first partition set
$n$ = Number of vertices in the second partition set
$|E|$ = Total number of edges in the graph

How It Works

To construct

K_{m,n}

, create two sets of vertices — one with

m

vertices and one with

n

vertices. Then draw an edge from each vertex in the first set to every vertex in the second set, giving exactly

m \cdot n

edges total. No edges exist within either set. The graph

K_{1,n}

is called a star graph, and

K_{3,3}

plays a key role in Kuratowski's theorem for characterizing planar graphs.

Worked Example

Problem: Determine the number of edges in the complete bipartite graph K_{3,4} and list the degree of each vertex.

Step 1: Identify the partition sizes. The first set has 3 vertices and the second set has 4 vertices.

m = 3, \quad n = 4

Step 2: Compute the number of edges using the formula.

|E| = m \cdot n = 3 \times 4 = 12

Step 3: Each vertex in the first set is adjacent to all 4 vertices in the second set, so it has degree 4. Each vertex in the second set is adjacent to all 3 vertices in the first set, so it has degree 3.

\deg(v) = \begin{cases} 4 & \text{if } v \in V_1 \\ 3 & \text{if } v \in V_2 \end{cases}

Answer: K_{3,4} has 12 edges. The 3 vertices in V₁ each have degree 4, and the 4 vertices in V₂ each have degree 3.

Why It Matters

Complete bipartite graphs appear in matching theory, network design, and algorithm analysis. The graph

K_{3,3}

is one of two fundamental obstructions to planarity in Kuratowski's theorem, making it essential in topology and graph theory courses. They also model real scenarios like job assignments, where every applicant must be compared against every open position.

Common Mistakes

Mistake: Confusing

K_{m,n}

with the complete graph

K_n

, which connects every pair of vertices regardless of partition.

Correction:

K_n

has

\binom{n}{2}

edges among

n

vertices with no partition restriction.

K_{m,n}

has

m \cdot n

edges and only connects vertices across the two parts, never within the same part.