How is a bottleneck defined in this video?

Conditions

• S is a subset of the left-side vertices.
• $E(S)$ is the neighborhood of S in the right-side set.

Reasoning, step by step

1. Take an arbitrary subset S of the left-side vertices.
2. Calculate the size of S, denoted |S|.
3. Calculate the size of its neighborhood $E(S)$, denoted |$E(S)$|.
4. Compare the two sizes: if |S| > |$E(S)$|, then S is a bottleneck.

Example

The slide shows |S| = 3 and 2 = |$E(S)$|, and later states |S| > |$E(S)$|. The speaker says, "the definition of a bottleneck is that if you have a set where the size of S is greater than the size of the image of S, then that's called a bottleneck."

Common misconceptions

• Thinking that a bottleneck means the entire graph has too few vertices on the right side.
• Assuming that |S| >= |$E(S)$| is sufficient to be a bottleneck.

Watch the explanation

Explore next

• What does the Bottleneck Lemma say?
• Why does the three-girls/two-boys example prove no matching is possible?