Graph Theory37 sections · 1633 units
Open in Course

What Is a Bipartite Graph?

Core definition

A bipartite graph is one where you can split all nodes into two groups such that every edge connects a node from one group to a node in the other. No edge connects two nodes within the same group. Picture a job fair: one group is candidates, the other is companies. Every connection (edge) links a candidate to a company.

No candidate connects to another candidate. No company connects to another company. Not every graph has this property. A triangle fails because no matter how you split three mutually connected nodes, at least one edge stays inside a group.