Bipartite graph - Definition and Overview

In the mathematical field of graph theory, a bipartite graph is a special graph where the set of vertices can be divided into two disjunct sets with two vertices of the same set never sharing an edge.

Bipartite graphs are useful for modelling matching problems. An example is a job matching problem. Suppose we have a set of people P and a set of jobs J, with not all people suitable for all jobs. We can model this as a graph with P + J the set of vertices. If a person <math>p_i<math> is suitable for a certain job <math>j_i<math> there is a edge between <math>p_i<math> and <math>j_i<math> in the graph.

Definitions

A simple undirected graph <math>G:=(V,E)<math> is called bipartite if there exists a partition of the vertex set <math>V=V_1 \cup V_2 <math> so that both <math>V_1<math> and <math>V_2<math> are independent sets. We often write <math>G:=(V_1 + V_2, E)<math> to denote a bipartite graph with partitions <math>V_1<math> and <math>V_2<math>.

A complete bipartite graph or biclique is bipartite graph such that for any two vertices <math>v_1 \in V_1<math> and <math>v_2 \in V_2<math> <math>v_1 v_2<math> is an edge in G. A complete bipartite graph with partitions of size <math>\|V_1\|=m<math> and <math>\|V_2\|=n<math> is denoted <math>K_{m,n}<math>.

Examples

• every tree is bipartite

Complete bipartite graphs

Notes

A planar graph cannot contain <math>K_{3,3}<math> as a minor.