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.

Contents

1 Definition

2 Examples

3 Properties

4 See also

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

Missing image
Complete_bipartite_graph_K3,1.png

K_3,1

Missing image
Complete_bipartite_graph_K3,2.png

K_3,2

Missing image
Complete_bipartite_graph_K3,3.png

K_3,3

Properties

A planar graph cannot contain $K 3,3$ as a minor; an outerplanar graph cannot contain $K 2,3$ as a minor. (These are not sufficient conditions for planarity and outerplanarity, but necessary.)
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}$
A complete bipartite graph $K n, n$ has a proper n-edge-coloring
The last two results are corollaries of the Marriage Theorem as applied to a k-regular bipartite graph

Complete bipartite graph

Definition

Examples

Properties

See also

See also: Complete bipartite graph, Bipartite graph, Complete graph, Corollary, Edge coloring, Edge covering number, Graph theory, Marriage Theorem, Mathematical, Maximum independent set