Bipartite Graphs

Split the vertices into two camps, send every edge across, and odd cycles instantly become the villain.

The idea

A graph is bipartite if its vertex set can be split into two disjoint pieces — the two parts — so that every edge has one endpoint in each part; equivalently, no edge has both endpoints in the same part. Such graphs arise whenever the vertices come in two types. With students and courses as vertices, and an edge joining each student to each course they take, every edge runs from a student to a course. Timetabling, assignment and matching problems all have this shape.

The definition is an existence claim: a bipartite graph does not come labelled with its split, and the requirement is only that some split works. Exhibiting a split settles the matter; showing that no split works needs an argument rather than a search, since there are $2^{n}$ splits to rule out.

Two further definitions accompany this one. A cycle is a closed walk along edges that returns to its starting vertex and repeats no other, and its length is the number of edges it uses. The complete bipartite graph $K_{m,n}$ has parts of sizes $m$ and $n$ and every one of the $mn$ possible cross edges. The figure shows $K_{2,3}$: its parts are the left vertices $L_{1}, L_{2}$ and the right vertices $R_{1}, R_{2}, R_{3}$, and every edge runs between the two columns.

Ways to work on it

• Walkthrough. Meet bipartite graphs through cycles, triangles, and K_m,n.
• Practice. Classify small graphs as bipartite or not.
• Hardest. Count edges in K_m,n and connect bipartite structure to triangle-freeness.

Not sure where to start? Take the ten-question placement test.