Definition:Bipartite Graph
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:
and
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
Also see
- Results about bipartite graphs can be found here.
Sources
- 2008: John M. Harris, Jeffry L. Hirst and Michael J. Mossinghoff: Combinatorics and Graph Theory (2nd ed.): $\S 1.1$
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): graph: 2.
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): graph: 2.
- 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): bipartite graph