On a bipartite eligibility graph, why does the largest possible pairing also fix the smallest set of vertices touching every edge?
answer
- one picks edges, one picks vertices
- disjoint pairs need distinct cover vertices
- cover is never the smaller of the two
- equality is a bipartite privilege
- triangle gives one against two
basics
~10 sA vertex cover needs a distinct vertex for each pair of a matching, so no cover is smaller than the largest matching. Konig's theorem says that on bipartite graphs the two are exactly equal.
solid answer
~40 sA **vertex cover** is a set of vertices - items or engineers - touching every eligibility edge. In any graph the pairs of a matching are vertex-disjoint, so a cover must spend at least one distinct vertex on each of them, giving `cover >= matching`. **Konig's theorem** says that when the graph is bipartite the inequality is tight: the minimum vertex cover and the maximum matching have the same size. That is a duality statement, and its value is that the cover is a *checkable proof* of the matching's optimality - anyone can verify that a cover of size `k` touches every edge, and that instantly rules out a matching of size `k + 1`. The equality is genuinely bipartite: a triangle has maximum matching 1 and minimum vertex cover 2.
go deeper
Recall the two words: a matching picks pairs that share nobody, a vertex cover picks people so that every eligibility link has someone chosen at one end.
Explain the easy inequality - disjoint pairs force distinct cover vertices - and state that equality is a property of bipartite graphs rather than of graphs in general.
Use the cover as a verifiable certificate of optimality, and be ready with the triangle as the counterexample when someone generalises the equality beyond bipartite graphs.
Treat the minimum cover as the diagnostic artefact: it names the small set of items and specialists on which all eligibility concentrates, which is where cross-training or hiring actually changes the ceiling.
## Two quantities, one bipartite graph The graph is the eligibility graph: items on one side, engineers on the other, an edge where an engineer may take an item. Two numbers live on it. - The **maximum matching** is the largest set of edges no two of which share a vertex - the most items that can be staffed simultaneously. - The **minimum vertex cover** is the smallest set of vertices such that every edge has at least one endpoint in the set - the smallest group of items-and-engineers that "touches" every eligibility relation. They look unrelated: one picks edges, the other picks vertices; one is a maximisation, the other a minimisation. **Konig's theorem** says that on a bipartite graph they are equal. ## The easy inequality holds everywhere One direction needs no bipartiteness at all. Take a matching `M` and a vertex cover `C`. Every edge of `M` must be touched by `C`, so `C` contains an endpoint of each. The edges of `M` share no endpoints, so those chosen vertices are all different. Hence `|C| >= |M|` in **every** graph, for every matching and every cover - and therefore `minimum cover >= maximum matching`. This half alone is already useful: exhibit any cover of size `k` and you have proved no matching exceeds `k`. ## Where the equality holds and where it breaks | Graph | Maximum matching | Minimum vertex cover | Equal? | |---|---|---|---| | Items `A, B`; engineers `X, Y`; edges `A-X, A-Y, B-X` | 2 (`A-Y`, `B-X`) | 2 (`A` and `X`) | Yes - bipartite | | A triangle on three vertices | 1 | 2 | No - contains an odd cycle | | Any bipartite graph | `m` | `m` | Yes, by Konig's theorem | The triangle is the smallest counterexample and worth carrying in your head. Three mutually adjacent vertices give only one disjoint edge, since any second edge would reuse a vertex, while one vertex leaves the opposite edge untouched, so the cover needs two. The gap is a consequence of the odd cycle, which is exactly the structure bipartite graphs exclude. In general graphs the two quantities can never be more than a factor of two apart, because the endpoints of any maximal matching already form a cover. Bipartiteness is what collapses that factor to one. ## Why duality is the point, not the arithmetic The equality is worth knowing for what it does to an *argument*, not for the number. Consider three situations: 1. **Proving optimality cheaply.** Verifying that a proposed matching is maximum would otherwise mean reasoning about all other matchings. With a cover of the same size in hand, the check is local: confirm every edge is touched, count the vertices, done. 2. **Explaining the bottleneck.** A minimum cover is a small set of items and engineers on which all eligibility is concentrated. Reading it tells you *where* the scarcity is, which a count of unstaffed items does not. 3. **Getting an independent set for free.** The complement of a vertex cover is an **independent set** - a set of vertices with no edge between any two. So the largest independent set has size `n - (minimum cover)`, and on a bipartite graph that is `n` minus the maximum matching. In staffing terms, that is the largest group of items and engineers with no eligibility relation between them at all. ## Careful statements that are easy to get backwards Four distinctions cause most of the errors here: - **Cover every edge, not every vertex.** A vertex cover touches all *edges*. An isolated vertex is in no edge and never needs to be covered. - **Vertex cover is not edge cover.** An edge cover is a set of *edges* touching every vertex; it is a different quantity with a different relationship to the matching. - **The cover may mix both sides.** Nothing forces a minimum cover to consist only of engineers or only of items; in the three-edge example it is one item and one engineer. - **The direction of the easy inequality.** Cover is at least matching, never the other way round. A cover smaller than the matching is impossible in any graph, so a claim to have found one is an arithmetic error. Finally, keep the scope honest. Konig's theorem is a statement about bipartite graphs. On general graphs the equality simply fails, as the triangle shows, and the question of how hard the minimum cover is to compute there belongs to complexity theory rather than to graph structure.
- Why is a vertex cover never smaller than a matching, in any graph at all?Because the edges of a matching are pairwise vertex-disjoint, and the cover must touch each of them. The endpoints it spends on one matched edge cannot serve any other, so the cover needs at least one distinct vertex per matched edge. That argument uses nothing about bipartiteness, which is why the inequality is universal while the equality is not.
- Give a graph where the two quantities genuinely differ.A triangle. Any two of its edges share a vertex, so the maximum matching is one edge, while a single vertex leaves the opposite edge untouched, so the minimum cover is two. The odd cycle is the obstruction, and bipartite graphs have none, which is precisely the hypothesis Konig's theorem needs.
- What does the complement of a minimum vertex cover give you?A maximum independent set - a largest collection of vertices with no edge between any two - because removing a cover removes at least one endpoint of every edge. So on a bipartite graph the largest independent set has size `n` minus the maximum matching.
A cover is a set of guards posted on junctions so that every road has a guard at one end; disjoint roads need separate guards, which is why the guard count can never fall below the number of disjoint roads.
saying these in an interview costs you the question
- Claims matching equals cover in every graph rather than bipartite ones
- Believes a cleverly chosen cover can come out smaller than the matching
- Insists a minimum cover must be drawn from one side only
- Confuses covering every edge with covering every vertex
- Treats a vertex cover and an edge cover as the same quantity