BIGpedia - Complete bipartite graph - Encyclopedia and Dictionary Online

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.

Contents

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{m, n}$ and an edge covering number of $max{m, n}$
A complete bipartite graph $K m, n$ has a maximum independent set of size $max{m, n}$
A complete bipartite graph $K m, n$ has a perfect matching of size $min{m, n}$