Bipartite Graph

Topics: Graph - Graph Theory

---

(definition)

A bipartite graph $G$ is a graph whose set of vertices $V$ can be partitioned in two subsets $U$ and $W$, such that every edge of $G$ joins a vertex in $U$ and another one in $W$.

The pair $\{U,W\}$ is called a bipartition of $G$, and $U,W$ are called the subsets of the bipartition.

As the name suggests, a bipartite graph’s partition only contains two subsets.

Example

The following graph is bipartite since $\{U,W\}=\{\{A,C\},\{B,D\}\}$ is a partition of $V$ that satisfies the necessary conditions.

We can also have complete bipartite graphs.

Theorems §

(theorem)

A bipartite graph can’t have any loops.

(theorem)

The smallest simple graph that is not bipartite is the $K_3$ complete graph.