Graphs · step 4 of 14

Bipartite graphs & colouring basics

A graph is bipartite when its vertices split into two sets with every edge crossing between them — equivalently, when it is 2-colourable. König’s characterisation makes testing easy: a graph is bipartite if and only if it contains no odd cycle. So finding a triangle or any odd closed walk immediately proves a graph is not bipartite.

Practise bipartite graphs & colouring basics free → All Graphs subtopics

✓ Unlimited questions · marked criterion by criterion · no card needed

Method: how to approach it

The order below is what examiners expect to see, and each step carries its own marks.

Try to 2-colour by BFSColour a start vertex, colour all its neighbours the opposite colour, and continue level by level.
Look for a conflictAn edge joining two same-coloured vertices means an odd cycle exists and the graph is not bipartite.
Hunt odd cycles directlyAny triangle, pentagon or odd closed walk is a complete disproof of bipartiteness.
Name the two partsFor a positive answer, exhibit the bipartition explicitly and check every edge crosses it.

Worked example

Is the cycle C₅ bipartite? What about C₆?

C₅ has five vertices in a cycle. 2-colour alternately: 1 red, 2 blue, 3 red, 4 blue, 5 red.
But vertex 5 is adjacent to vertex 1, and both are red — conflict.
C₅ is an odd cycle, so no 2-colouring exists.
C₆ alternates cleanly: red, blue, red, blue, red, blue, and vertex 6 (blue) meets vertex 1 (red) ✓.

Answer. C₅ is not bipartite (it is an odd cycle); C₆ is bipartite, with parts {1,3,5} and {2,4,6}.

Where marks get dropped

These are the specific errors that cost credit on bipartite graphs & colouring basics questions — QED's rubric penalises each of them separately.

Assuming a graph with no triangle is bipartite. C₅ is triangle-free and not bipartite — every odd cycle length must be excluded.
Checking only one component. A disconnected graph is bipartite iff every component is, and each needs its own colouring.
Confusing "bipartite" with "complete bipartite". K_{3,3} is a specific bipartite graph, not the definition.

Practise this until it is automatic

Unlimited fresh questions

QED generates new bipartite graphs & colouring basics problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.

Marked like an examiner

Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.

Answer in real notation

A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.

Saved to your library

Every question you generate is kept and re-takeable as a timed exam, and your Graphs mastery is tracked so you know when this is exam-ready.

Bipartite graphs & colouring basics — frequently asked questions

Why does no odd cycle imply bipartite?

Colour each vertex by the parity of its distance from a fixed root. Any edge joining two same-parity vertices would close an odd cycle, so no such edge exists.

What is K_{m,n}?

The complete bipartite graph with all m·n possible crossing edges. K_{3,3} is famous for being non-planar.

How fast can bipartiteness be tested?

O(V + E) with a single BFS or DFS that colours as it goes and reports the first conflict.

The rest of Graphs

Terminology, connectivity, trees, paths and cycles. Each subtopic below has its own method, worked example and mark-losing traps.

Ready to make bipartite graphs & colouring basics exam-proof?

Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.

Start practising free →