IsBipartite - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

GraphTheory

 IsBipartite
 test if graph is bipartite

 Calling Sequence IsBipartite(G) IsBipartite(G, P)

Parameters

 G - graph P - (optional) name

Description

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

Examples

 > $\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 edge\left(s\right)}}$ (1)
 > $\mathrm{IsBipartite}\left(\mathrm{K32},'\mathrm{bp}'\right)$
 ${\mathrm{true}}$ (2)
 > $\mathrm{bp}$
 $\left[\left[{1}{,}{2}{,}{3}\right]{,}\left[{4}{,}{5}\right]\right]$ (3)
 > $\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]$ (4)
 > $G≔\mathrm{CycleGraph}\left(5\right)$
 ${G}{≔}{\mathrm{Graph 2: an undirected graph with 5 vertices and 5 edge\left(s\right)}}$ (5)
 > $\mathrm{IsBipartite}\left(G\right)$
 ${\mathrm{false}}$ (6)