IsBipartiteGraph

Whether a Graph's vertices split into two sets with every edge crossing between them.

✓ checked against that system · ! checked, with disagreements (hover a chip)Wolfram LanguageBipartiteGraphQ✓↗

IsBipartiteGraph(g)true iff a 2-colouring exists (BFS, underlying graph, direction ignored) — false for any graph with an odd cycle, including a self-loop.

Typed signatures

Type	Package	Applies
(value) -> boolean	combinatorics	always

Domain: Collections

Details

• Wolfram calls this BipartiteGraphQ; this library uses the Is… spelling everywhere.

Examples

2 more kept as data, checked against the oracles

Basic #

live ↗

In$\mathrm{IsBipartiteGraph}(\mathrm{CycleGraph}(6))$Out$\mathrm{True}$

live ↗

In$\mathrm{IsBipartiteGraph}(\mathrm{CycleGraph}(5))$Out$\mathrm{False}$

live ↗

In$\mathrm{IsBipartiteGraph}(\mathrm{Graph}(\bigl\lbrack\mathrm{UndirectedEdge}(1, 1)\bigr\rbrack))$Out$\mathrm{False}$

Properties #

A triangle is an odd cycle, so it cannot be two-coloured

live ↗

In$\mathrm{IsBipartiteGraph}(\mathrm{CycleGraph}(3))$Out$\mathrm{False}$

About

Examples	6
Checked against	Wolfram Language 5 agree
Crosswalk	Wolfram Language

See also: IsConnectedGraph, CycleGraph