Bipartite graph

Definition

Let $G$ be a graph 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 with $2$ colours. The complete bipartite graphs, the even cycle graphs and all trees 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 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.