IsBipartite returns true if the graph G is bipartite and false otherwise. If a variable name P is specified, then this name is assigned a bipartition of the vertices as a list of lists.

A graph G is bipartite if its set of vertices can be partitioned into two sets, $V_1$ and $V_2$, such that every edge in G connects a vertex in $V_1$ or $V_2$ to a vertex in the other set.

$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$

$\mathrm{K32}≔\mathrm{CompleteGraph}\left(3\,2\right)$

$\mathrm{K32}≔\mathrm{Graph\; 1:\; an\; undirected\; graph\; with\; 5\; vertices\; and\; 6\; edges}$

$\mathrm{IsBipartite}\left(\mathrm{K32}\,'\mathrm{bp}'\right)$

$\mathrm{true}$

$\mathrm{bp}$

$\left[\left[1\,2\,3\right]\,\left[4\,5\right]\right]$

$\mathrm{DrawGraph}\left(\mathrm{K32}\,\mathrm{style}=\mathrm{bipartite}\right)$

$\mathrm{AdjacencyMatrix}\left(\mathrm{K32}\right)$

$\left[\begin{array}{ccccc}0& 0& 0& 1& 1\\ 0& 0& 0& 1& 1\\ 0& 0& 0& 1& 1\\ 1& 1& 1& 0& 0\\ 1& 1& 1& 0& 0\end{array}\right]$

$G≔\mathrm{CycleGraph}\left(5\right)$

$G≔\mathrm{Graph\; 2:\; an\; undirected\; graph\; with\; 5\; vertices\; and\; 5\; edges}$

$\mathrm{IsBipartite}\left(G\right)$

$\mathrm{false}$