# Bipartite Graph **A [[graph]] whose vertices can be [[Partition|partitioned]] into two [[disjoint sets]] both of which contain no adjacent vertices.** ![[BipartiteGraph.svg|500]] *A bipartite graph; the vertices are coloured according to their set* > [!NOTE] Bipartite Graph > A *bipartite graph* $G(V, W, E)$ consists of two *disjoint sets* of vertices, $V$ and $W$, and a set of edges $E$ that connect an element of $V$ to one in $W$. Vertices of the same set never share a common edge in a bipartite graph. An equivalent definition for a bipartite graph is an undirected graph that *does not* contain any *odd* [[Cycle|cycles]]. ## Complete bipartite graph A *[[Complete Graph|complete]] bipartite graph* $G(V, W, E)$ is denoted $K_{m,n}$ where $V$ and $W$ contain $m$ and $n$ vertices respectively. It has $m + n$ vertices and $mn$ edges. ![[CompleteBipartiteGraph.svg|500]] *A complete bipartite graph, $K_{4,3}$*