What is a bipartite graph according to the video?

Conditions

• The graph is a simple graph.
• The vertex set is partitioned into two disjoint subsets.
• The two endpoints of each edge belong to opposite sides.

Reasoning, step by step

1. Identify the two disjoint sets of vertices.
2. Verify that every vertex belongs to exactly one set.
3. Check that every edge connects a vertex from the first set to a vertex from the second set.

Example

The video shows two separate ellipses, one holding the G vertices and the other the B vertices, and then draws only edges crossing between the ellipses.

Common misconceptions

• Thinking that a bipartite graph only requires vertices to be split into two groups, while edges could still connect arbitrarily.
• Assuming that edges can connect vertices within the same side.

Watch the explanation

Explore next

• What exactly does the bipartite matching problem require?
• Why formalize matching as an edge-following bijection from girls to boys?