---
tag: 07DVHJ8N0A
kind: definition
name: Bipartite graph
msc: [05C75]
defines: 0ZVQKTRKVQ
sources:
  - url: https://en.wikipedia.org/wiki/Bipartite_graph
    locator: lead section
---

## Definition

Let $G$ be a [[graph|0JD5C82QMB]] with vertex set $V$.
Then $G$ is bipartite if $V$ is the union of two disjoint sets $A$ and $B$ with this property.
Each edge of $G$ has one end in $A$ and one end in $B$.
The pair $(A, B)$ is a bipartition of $G$.

## Remarks

Equivalently, $G$ is bipartite if it has a proper [[colouring|0874138YP6]] with $2$ colours.
The [[complete bipartite graphs|0V0GC7BQAN]], the even [[cycle graphs|0QQ0F12962]] and all [[trees|0MJ0JS72DZ]] are bipartite.
A graph is bipartite if and only if it has no cycle of odd length. The node [[a graph is bipartite iff it has no odd cycle|01R1HPEK6S]] states this.

## Explanations

### L1 human

A graph is bipartite when its vertices split into two groups, and every edge goes between the groups.
Students and the courses they take form a bipartite graph.