Skip to content

Bipartite Graphs: The Two-Colour Test and the Odd-Cycle Rule

A graph is bipartite when its vertices split into two sides with every edge crossing between. How to test it, why odd cycles rule it out, and matchings.

By Published 5 min read

Reign Creative LLC makes Discrete Math: Study & Quiz, which this article links to, so we have a commercial interest in it. How we write and check articles.

AI-assisted article. Drafted with AI tools from the sources cited below and checked by automated tests and an AI editorial review. No person has reviewed it yet. How we write and check articles.

Key takeaways

  • A graph is bipartite if its vertices split into two sets with every edge joining a vertex in one set to a vertex in the other.
  • Bipartite graphs are exactly the graphs that can be properly colored with two colors.
  • A graph is bipartite if and only if it has no cycle of odd length; finding one odd cycle proves it is not.
  • To test a graph, color a vertex, give all its neighbours the other color, and continue; a clash means it is not bipartite.
  • Bipartite graphs model assignments, such as workers to jobs, and Hall's theorem says when everyone on one side can be matched.

Some networks connect two different kinds of thing: applicants and jobs, students and courses, customers and products, actors and films. Edges only ever join one kind to the other, never two of the same kind. Graphs with that shape are bipartite, and they have a clean characterisation, a fast test, and an important theorem about matching.

Two sides, edges only between them

A graph is bipartite if its vertex set can be split into two disjoint sets, often called X and Y, so that every edge has one end in X and one end in Y. No edge joins two vertices on the same side.

The complete bipartite graph Kₘ,ₙ has m vertices on one side, n on the other, and every possible edge between the sides, mn edges in all. K₃,₃ is the graph behind the classic puzzle of joining three houses to three utilities.

Bipartite means two-colourable

Colour the vertices in X red and those in Y blue. Every edge joins a red vertex to a blue one, so this is a proper colouring with two colours. Conversely, any proper 2-colouring splits the vertices into two colour classes with every edge between them. So:

A graph is bipartite exactly when it can be properly coloured with two colours.

MathWorld states the equivalence directly, and Levin's Discrete Mathematics: An Open Introduction uses it in its colouring section: K₂,₃, like all bipartite graphs, has chromatic number 2. The wider theory of colouring is in graph colouring and the chromatic number.

The odd-cycle rule

A graph is bipartite if and only if it contains no cycle of odd length. MathWorld gives this criterion too.

Why odd cycles are impossible. Walk around a cycle in a bipartite graph. Each step crosses from one side to the other. After an odd number of steps you are on the opposite side from where you started, so you cannot be back at the starting vertex. Every cycle must have even length.

Why no odd cycles is enough. Work in one connected component and pick a vertex r. Put each vertex on side X or Y according to whether its distance from r is even or odd. If some edge joined two vertices at even distance, or two at odd distance, the shortest paths from r to its ends, plus that edge, would close up into a walk containing an odd cycle. With no odd cycles, every edge joins an even-distance vertex to an odd-distance one, and the split works.

Consequences.

  • Every tree is bipartite, having no cycles at all. MathWorld notes that all acyclic graphs are bipartite.
  • An even cycle is bipartite; an odd cycle, including a triangle, is not.
  • Any graph containing a triangle is not bipartite.

Testing a graph: colour as you go

The proof above is also an algorithm.

  1. Pick an uncoloured vertex and colour it red.
  2. Colour all its neighbours blue, then all their uncoloured neighbours red, and so on, alternating.
  3. Whenever an edge joins two vertices of the same colour, stop: the graph is not bipartite, and that edge closes an odd cycle you can point to.
  4. Repeat for each connected component.

Example. Vertices 1 to 6 with edges 12, 23, 34, 45, 56, 61 and 14. Colour 1 red. Then 2, 6 and 4 are blue (neighbours of 1). Then 3 and 5 are red (neighbours of 2, 4 and 6). Check every edge: 12, 23, 34, 45, 56, 61 and 14 all join red to blue. Bipartite, with sides {1, 3, 5} and {2, 4, 6}. Add the edge 13, and 1 and 3 are both red: the cycle 1–2–3–1 is a triangle, so the new graph is not bipartite.

Matchings and Hall's theorem

In a bipartite graph with sides A and B, a matching is a set of edges with no shared ends: each vertex is used at most once. A matching of A pairs every vertex in A with a different vertex in B. Think of A as workers, B as jobs, and edges as "can do". Can every worker get a different job?

Levin presents the answer as Hall's marriage theorem, first proved by Philip Hall in 1935: a bipartite graph has a matching of A if and only if every set S of vertices in A has at least |S| neighbours in B.

The condition is clearly necessary: if three workers can between them do only two jobs, they cannot all be employed. The theorem says that this is the only obstacle. Levin sums up the spirit of it: if you can avoid the obvious counterexamples, you often get what you want.

Example. Workers Ana, Ben and Cal; jobs X, Y and Z. Ana can do X or Y; Ben can do X only; Cal can do Y or Z. Check Hall's condition for every group of workers: each individual can do at least one job; {Ana, Ben} can do X and Y; {Ana, Cal} can do X, Y and Z; {Ben, Cal} can do X, Y and Z; all three can do X, Y and Z. The condition holds, so a matching exists: Ben–X, Ana–Y, Cal–Z.

Where bipartite structure matters elsewhere

  • Hamiltonian cycles. A cycle alternates sides, so it uses equally many vertices from each. A bipartite graph with unequal sides, such as K₂,₃, has no Hamiltonian cycle, one of the obstructions listed in Hamiltonian paths and cycles.
  • Planarity. K₃,₃ cannot be drawn in the plane without crossings, a fact proved with Euler's formula in planar graphs.

Three graphs to test

  1. Is the cube graph (vertices are 3-bit strings, edges join strings differing in one bit) bipartite? (Yes: split by whether the number of 1s is even or odd.)
  2. Is C₇ bipartite? (No: it is an odd cycle.)
  3. How many edges does K₄,₅ have? (20.)

Bipartite graphs belong to the graph theory unit of Discrete Math: Study & Quiz, the last unit in the app's sequence. It is listed with our education apps, and the discrete math hub links the neighbouring graph guides, including trees and graph basics.

Good to know

Frequently asked questions

What is a bipartite graph?
A graph whose vertices can be divided into two groups so that every edge goes between the groups and none stays inside a group. Students and the courses they take, or workers and the jobs they can do, naturally form bipartite graphs.
How do you tell if a graph is bipartite?
Try to 2-color it. Give any vertex color A, all its neighbours color B, their neighbours color A, and so on through each connected component. If you never have to give two adjacent vertices the same color, the graph is bipartite; a clash exposes an odd cycle and shows it is not.
Why can't a bipartite graph contain an odd cycle?
Walking around a cycle in a bipartite graph, every step crosses from one side to the other. To return to the starting vertex, on its original side, you must take an even number of steps. So every cycle has even length.
Are trees bipartite?
Yes. A tree has no cycles at all, so it certainly has no odd cycles. Concretely, choose a root and put vertices at even depth on one side and odd depth on the other; every edge joins consecutive depths.

Sources

  1. Bipartite Graph (opens in a new tab)Wolfram MathWorld — accessed
  2. Matching in Bipartite Graphs (Discrete Mathematics: An Open Introduction, 3rd edition, Oscar Levin) (opens in a new tab)Open Math Books — accessed
  3. Coloring (Discrete Mathematics: An Open Introduction, 3rd edition, Oscar Levin) (opens in a new tab)Open Math Books — accessed

About the author

— The independent app studio that builds the apps covered on this site and publishes every article here. On Google Play it publishes as Reign Collective Apps.

We use AI tools to help research, draft and edit our articles. Each article lists the sources its factual claims rely on, and details about our apps come from their live Google Play listings. No article on this site has been reviewed by an independent expert unless the reviewer is named on it.

No person at Reign Creative LLC has read this article in full. It was published after automated checks and an AI editorial review, which are described in our editorial policy and are not the same as a person reading every sentence.

Spotted an error? Tell us — how corrections are handled is set out in our editorial policy.

Keep reading