Partition
V = A ∪ B, A ∩ B = ∅
Every vertex belongs to exactly one side.
Bipartite Graph Checker and Two-Coloring Visualizer
Enter an undirected graph
Private by design: graph parsing, two-coloring, visualization, copying, and export happen on this device. Input is not uploaded, stored, or added to the page URL.
Set ASet BOdd-cycle witness
Check a graph to display its two-coloring or odd-cycle witness.
| Vertex | BFS side | Degree | Component |
|---|---|---|---|
| No graph checked yet. | |||
Advertisement
What is a bipartite graph?
A graph is bipartite when its vertex set can be partitioned into two disjoint sets, often called A and B, so every edge has one endpoint in each set. Equivalently, a graph is bipartite exactly when it has a proper vertex coloring using at most two colors.
Edge condition
{u,v} ∈ E ⇒ color(u) ≠ color(v)
Every edge crosses between the two colors.
Cycle test
G is bipartite ⇔ G has no odd cycle
An odd cycle is a certificate that no two-coloring exists.
The two sets are not necessarily unique. Each connected component can have its colors swapped independently. Isolated vertices may be put on either side because they have no edge constraint.
How the two-coloring algorithm works
1. Start a component
Choose an uncolored vertex, assign it to Set A, and put it in a first-in, first-out queue.
2. Alternate colors
Remove a vertex from the queue. Every uncolored neighbor receives the opposite color and enters the queue.
3. Detect a conflict
If an edge joins two vertices of the same color, their breadth-first parent paths combine with that edge to form an odd cycle.
4. Check every component
Repeat from each still-uncolored vertex so disconnected components and isolated vertices are included.
The graph is stored as adjacency lists. Parsing aside, the check takes O(|V| + |E|) time and O(|V| + |E|) space because each vertex and edge is processed a constant number of times.
Bipartite and non-bipartite examples
Paths and even cycles
Every path is bipartite. An even cycle alternates colors and returns to its starting vertex consistently; the sample square therefore has a valid two-coloring.
Odd cycles
A triangle, five-cycle, or any other odd cycle is not bipartite. Select Load odd cycle to see a five-edge witness highlighted in red.
Trees and forests
Every tree and forest is bipartite. With a chosen root, vertices at even distance form one set and vertices at odd distance form the other.
Complete bipartite graphs
In Km,n, each of the m vertices on one side is adjacent to all n vertices on the other, with no edges within either side.
Input rules, assumptions, and limits
Vertex labels are case-sensitive text. The optional vertex field accepts commas, semicolons, or line breaks. Edge endpoints are detected automatically, but isolated vertices must be listed explicitly. Enter one undirected edge per line as left,right. Whitespace around a label is ignored while spaces inside it are retained.
Repeated edges, including reversed duplicates, are merged and reported. A self-loop is accepted as graph data and correctly makes the graph non-bipartite; it is reported as an odd cycle of length one. Directed arrows and edge weights are rejected because this checker uses undirected adjacency.
The checker accepts up to 500 vertices, 20,000 nonempty edge lines, 50,000 distinct edges, and labels up to 80 characters. For responsiveness, the SVG draws at most 120 vertices and 1,200 edges, while the bipartite result and exported table still cover the entire accepted graph.
The definition follows the U.S. National Institute of Standards and Technology’s Dictionary of Algorithms and Data Structures entry for bipartite graph. The checker uses a queue-based breadth-first search and explicitly reconstructs a conflicting odd cycle.
Calculation note: even and odd cycles, trees, disconnected graphs, isolated vertices, reversed duplicates, self-loops, invalid input, odd-cycle reconstruction, and size limits checked by the Starlight Tools editorial team. Last reviewed: .
Bipartite graph checker FAQ
What is a bipartite graph?
It is an undirected graph whose vertices can be split into two disjoint sets so every edge goes from one set to the other. This is the same as having a proper coloring with at most two colors.
How does the checker find a two-coloring?
It uses breadth-first search. A start vertex receives Set A, its neighbors receive Set B, their uncolored neighbors receive Set A, and so on. The process restarts for every disconnected component.
Why does an odd cycle prove a graph is not bipartite?
Colors must alternate around a cycle. An even cycle returns to the start with the opposite requirement satisfied; an odd cycle returns requiring the starting vertex to differ from itself, which cannot happen.
Can a disconnected graph be bipartite?
Yes. It is bipartite if every connected component is bipartite. The two colors may be swapped independently in each component, so several equally valid partitions can exist.
Are all trees bipartite?
Yes. Trees contain no cycles, so in particular they contain no odd cycle. Coloring by even and odd distance from a root produces a valid bipartition.
What happens with self-loops and duplicate edges?
A self-loop is an odd cycle of length one and makes the graph non-bipartite. Duplicate and reversed edges add no new constraint, so the checker merges them and reports how many were ignored.
Does this tool save or upload my graph?
No. Input parsing, breadth-first search, odd-cycle reconstruction, SVG rendering, copying, and CSV creation all happen locally in your browser.