# 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$. By the definition, vertices of a bipartite graph in the same set never share a common edge. 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 a bipartite graph in which every vertex is connected to every vertex of the other set. A complete bipartite graph with $m$ and $n$ vertices is denoted $K_{m,n}$, where $V$ and $W$ contain $m$ and $n$ vertices respectively. As such, a complete bipartite graph has $m + n$ vertices and $mn$ edges. ![[CompleteBipartiteGraph.svg|500]] *A complete bipartite graph, $K_{4,3}$*