Bipartite Graph Generator
A bipartite graph splits its nodes into two groups so that every edge runs between the groups and none inside them. That is exactly what matching problems, timetabling and any this-side-that-side question need. A graph is bipartite precisely when it contains no odd cycle, which makes a two-colouring search a complete test — and when it fails, this page shows the odd cycle responsible rather than just saying no.
What this generator does
Either builds a graph across a split so bipartiteness holds by construction, or builds a general graph and tests it. The test is a breadth-first two-colouring; when it meets an edge inside one side it walks both endpoints back to their common ancestor to recover the odd cycle.
How to use this tool
- Decide whether you want a graph that is bipartite or one that may not be.
- Choose the size and density.
- Find the split yourself, or read the two sides off the result.
- When a graph is not bipartite, trace the odd cycle that blocks it.
Understanding the controls
- Build one that is bipartite
- On, the graph is constructed across a split and always passes. Off, you get a general graph, which usually is not bipartite once it has a few extra edges.
- How many nodes
- Between 4 and 12, split roughly evenly between the two sides when bipartite construction is on.
- Extra edge density (%)
- Denser graphs are far more likely to contain an odd cycle, so turning density up makes bipartite examples rarer.
- Seed
- Reproduces exactly the same graph and split.
Common use cases
- Test instances for matching and assignment algorithms
- Showing why an odd cycle makes a two-colouring impossible
- Timetabling and scheduling examples in abstract form
- Practice at spotting a bipartite structure by eye
- Generating the same graph twice from a seed
How this generator works
Two-colouring assigns sides breadth-first and fails the moment an edge joins two nodes on the same side. The check requires every edge to cross the split on a bipartite result, and on a negative result requires the stated cycle to be odd, closed, and made only of edges the graph actually has.
Randomness and fairness
Which graph you get is random; whether it is bipartite is determined and proved either way. Seeded graphs reproduce exactly and are therefore explicitly not cryptographically secure, and unseeded ones use the browser's cryptographically secure generator.
For how randomness is produced across the whole site, see how Generate Random works.
Limitations and good to know
- Weights are generated but play no part — bipartiteness is a structural property.
- Only the two-sided case. Multipartite graphs with three or more groups are not generated.
- The odd cycle shown is the first one found, not the shortest.
- No drawing of the graph; sides are listed with the edge table.
- Graphs are not kept between visits.
Privacy and your data
The graph and its split are computed in your browser. Nothing about the graph or your seed leaves the page.
Related generators
- Graph Colouring Challenge GeneratorColour the nodes so no edge has one colour at both ends, with the greedy answer and — at small sizes — a proof that fewer colours are impossible.
- Random Graph GeneratorRandom graphs at a density you choose, drawn and exported as an edge list or DOT, with connectivity measured rather than assumed.
- Peer Review Pairing GeneratorBuild a one-way peer review ring where everyone reviews exactly one person, is reviewed by exactly one person, and never reviews their own reviewer.
- Minimum Spanning Tree GeneratorWeighted graphs with the cheapest spanning tree found by Kruskal and, at small sizes, confirmed against every other spanning tree.