complete bipartite graph

In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertices of the first set is connected to every vertex of the second set. Similar to complete graphs they have very nice properties.

Definition

A complete bipartite graph

G:=(V_1 + V_2, E)

is a bipartite graph such that for any two vertices

v_1 \in V_1

and

v_2 \in V_2

v_1 v_2

is an edge in

G

. A complete bipartite graph with partitions of size

\|V_1\|=m

and

\|V_2\|=n

is denoted

K_{m,n}

Examples

Properties

A planar graph cannot contain $K_{3,3}$ as a minor.
A complete bipartite graph $K_{m,n}$ has a vertex covering number of $\min \lbrace m,n \rbrace$ and an edge covering number of $\max \lbrace m,n \rbrace$
A complete bipartite graph $K_{m,n}$ has a maximum independent set of size $\max \lbrace m,n \rbrace$
A complete bipartite graph $K_{m,n}$ has a perfect matching of size $\min \lbrace m,n \rbrace$

Complete Bipartite Graph

Definition

Examples

Properties

See also