bipartite graph

In the mathematical field of graph theory, a bipartite graph is a special graph where the set of vertices can be divided into two disjoint 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

p_i

is suitable for a certain job

j_i

there is a edge between

p_i

and

j_i

in the graph. The marriage theorem provides a characterization of bipartite graphs which allow perfect matchings.

Definitions

A simple undirected graph

G:=(V,E)

is called bipartite if there exists a partition of the vertex set

V=V_1 \cup V_2

so that both

V_1

and

V_2

are independent sets. We often write

G:=(V_1 + V_2, E)

to denote a bipartite graph with partitions

V_1

and

V_2

Examples

every tree is bipartite
cycle graphs with an even number of vertices are bipartite
graphs with a vertex chromatic number of 2 are bipartite

Properties

a bipartite graph does not contain a odd cycle
the size of minimum vertex cover is equal to the size of the maximum matching
the size of the maximum independent set plus the size of the maximum matching is equal to the number of vertices.
for a connected bipartite graph the size of the minimum edge cover is equal to the size of the maximum independent set
for a connected bipartite graph the size of the minimum edge cover plus the size of the minimum vertex cover is equal to the number of vertices.

Bipartite Graph

Definitions

Examples

Properties

See also