Questions: König's Theorem and Min-Max Relations

Question 1

A graph has three vertices forming a triangle (K₃). A student claims: 'The maximum matching has size 1. By König's theorem, the minimum vertex cover should also have size 1.' What is wrong with this reasoning?

• A. The maximum matching of K₃ is actually size 2, not size 1
• B. König's theorem only applies to bipartite graphs; K₃ is an odd cycle and is not bipartite, so the theorem does not apply
• C. The minimum vertex cover of K₃ is size 1, confirming the student's claim
• D. König's theorem requires that the graph have a perfect matching

Answer: (B)

König's theorem is specific to bipartite graphs. In K₃, the maximum matching has size 1 (only one edge can be selected without sharing a vertex), but the minimum vertex cover has size 2 (any single vertex leaves one edge uncovered). The theorem fails here precisely because K₃ is an odd cycle, which cannot be bipartite. The bipartite structure is essential to the result.

Question 2

In a bipartite graph, why does maximum matching ≤ minimum vertex cover follow immediately from the definitions?

• A. Bipartite graphs always have more vertices than edges, guaranteeing the inequality
• B. Each edge in the matching is vertex-disjoint from every other matching edge, so each matching edge requires its own dedicated covering vertex
• C. The matching algorithm terminates before the vertex cover is fully constructed
• D. Vertex covers in bipartite graphs must include one entire partition

Answer: (B)

Matching edges are vertex-disjoint by definition — no two selected edges share an endpoint. This means a single vertex cannot cover two different matching edges. Therefore, to cover all k matching edges, the vertex cover needs at least k vertices. This gives the easy direction: maximum matching ≤ minimum vertex cover. The hard direction — that equality is always achievable in bipartite graphs — requires the constructive proof using augmenting paths.

Question 3

König's theorem states that in any graph, the size of a maximum matching equals the size of a minimum vertex cover.

• T. True
• F. False

Answer: False

König's theorem holds only for bipartite graphs. In non-bipartite graphs, the maximum matching can be strictly smaller than the minimum vertex cover. The triangle K₃ is the canonical counterexample: maximum matching = 1, minimum vertex cover = 2. The bipartite condition is not a technicality — it is the exact structural property that prevents odd cycles from breaking the min-max equality.

Question 4

In a bipartite graph, no single vertex can cover two edges from a maximum matching simultaneously, because matching edges share no endpoints by definition.

• T. True
• F. False

Answer: True

This is the key geometric fact behind the inequality max matching ≤ min vertex cover. Matching edges share no endpoints by the definition of a matching. Therefore each matching edge must be covered by a distinct vertex, and no vertex in the cover does double duty across two matching edges. This forces the cover to be at least as large as the matching.

Question 5

Explain why König's theorem fails on odd cycles like K₃ but holds for bipartite graphs. What property of bipartite graphs is essential?

Model answer: Bipartite graphs have no odd cycles — every cycle has even length. This two-colorability is what allows matchings and vertex covers to achieve equality in size. In an odd cycle like K₃, the three edges form a cycle that cannot be split into two independent sets with all edges crossing between them; this asymmetry means you need more vertices to cover all edges than you have edges in a maximum matching. Bipartite graphs avoid this: their LP relaxation is always integral (by total unimodularity), meaning the duality gap between the matching and cover problems is zero.

The connection to LP duality is the deeper explanation: matching and vertex cover are dual linear programs, and integrality of the LP solution is guaranteed for bipartite graphs but not for general graphs. For non-bipartite graphs, the LP optimal can be fractional, and the integer solutions diverge. Bipartiteness is not a convenience restriction — it is the exact condition under which combinatorial duality is tight.