Definition:Bipartite Graph

From ProofWiki
Jump to navigation Jump to search

Definition

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$.


Partite Set

Let $G = \struct {A \mid B, E}$ be a bipartite graph.


Then $A$ and $B$ are called the partite sets of $G$.


Examples

BipartiteGraphs.png


Also see

  • Results about bipartite graphs can be found here.


Sources