\begin{definition}[Definition:Bipartite Graph]
A '''bipartite graph''' is a graph $G = \struct {V, E}$ where:
:$V$ is partitioned into two sets $A$ and $B$ such that:
:each edge is incident to a vertex in $A$ and a vertex in $B$.
That is:
:no two vertices in $A$ are adjacent
and
:no two vertices in $B$ are adjacent.
It is a common practice when illustrating such a graph to draw the vertices of $A$ in one colour, and those of $B$ in another.
$G$ can be denoted $G = \struct {A \mid B, E}$ to emphasise that $A$ and $B$ partition $V$.
\end{definition}