König's Theorem and Vertex Covers

How few guards does it take to watch every road in a network? Suppose a graph represents intersections and edges represent roads. A vertex cover is a set of intersections. Every road must touch at least one chosen intersection. Finding the smallest such set is generally hard. It is one of Karp's original NP-complete problems. Yet in bipartite graphs, this question has a clean answer. The minimum number of guards equals the maximum number of pairwise non-adjacent roads. That is, it equals the size of a maximum matching. This equality is König's theorem. It was proved by Dénes Kőnig in 1931. An equivalent form was found independently by Jenő Egerváry the same year. It is the prototypical example of min-max duality in combinatorial optimization. A minimization problem (smallest vertex cover) meets a maximization problem (largest matching). They reach exactly the same value, whenever the underlying structure is bipartite. This is remarkable because for general graphs, matching number and vertex cover number can differ. A triangle already shows this. The theorem sits at the crossroads of several major threads in combinatorics. It is a close cousin of Hall's Theorem on systems of distinct representatives. It is also the bipartite special case of the deeper Tutte–Berge formula for general graphs. Additionally, it is one of the earliest instances of the linear programming duality phenomenon. That phenomenon later blossomed into the theory of Network Flows and Max-Flow Min-Cut. Understanding König's theorem is therefore a gateway backward, to matching theory. It is also a gateway forward, to the flow-based algorithms that dominate modern combinatorial optimization. This article gives the precise definitions of vertex cover, independent set, and matching. It states and rigorously proves König's theorem via an augmenting-path construction. It illustrates the theorem with two fully worked asymmetric examples. Finally, it shows exactly what fails — and why — once bipartiteness is dropped.

Key takeaways
  • A vertex cover is a set of vertices touching every edge; its minimum size is τ(G)\tau(G).
  • A matching is a set of pairwise disjoint edges; its maximum size is ν(G)\nu(G).
  • Always ν(G)≤τ(G)\nu(G) \le \tau(G) in any graph — a cover must "hit" every matching edge separately.
  • König's theorem: if GG is bipartite, then ν(G)=τ(G)\nu(G) = \tau(G) exactly.
  • The proof builds an explicit minimum cover from a maximum matching using alternating/augmenting paths.
  • Equality can fail badly outside bipartite graphs — the triangle has ν=1\nu = 1 but τ=2\tau = 2.
  • Key idea: in bipartite graphs, "hardest to cover" and "hardest to match" are the same number.

Where this lives today

König's theorem is the historical seed of combinatorial LP duality: the assignment problem (matching workers to jobs to minimize cost) and its dual formulation trace directly to Kőnig and Egerváry's work, and the Hungarian algorithm for the assignment problem is named in their honor. In computer science, König's theorem gives a polynomial-time algorithm for vertex cover and independent set restricted to bipartite graphs — a rare tractable special case of two problems that are NP-hard in general, and it underlies applications in scheduling, resource allocation, and bipartite matching markets. In Network Flows and Max-Flow Min-Cut, König's theorem reappears as a direct corollary: model the bipartite graph as a flow network with a source connected to XX, a sink connected from YY, and unit capacities; the max-flow min-cut theorem specializes exactly to the max-matching min-vertex-cover equality, showing König's result as the combinatorial ancestor of flow duality. The theorem also connects to statistics and design theory through its equivalence with Hall's Theorem (a special case of König's theorem when a perfect matching exists), and to the broader Tutte–Berge formula in general matching theory, which generalizes the min-max relationship using a correction term for odd components. In algebraic combinatorics, König's theorem is the combinatorial shadow of the fact that the vertex-edge incidence matrix of a bipartite graph is totally unimodular, a property responsible for the integrality of the associated linear program and hence for the exactness of the min-max identity.

Ask the tutor: How does König's theorem generalize to the Tutte–Berge formula for non-bipartite graphs, and what exactly is the "deficiency" correction term for odd components?

DefinitionVertex covers, independent sets, and matchings

Let G=(V,E)G = (V, E) be a finite, simple, undirected graph.

  • A vertex cover of GG is a set C⊆VC \subseteq V such that every edge e∈Ee \in E has at least one endpoint in CC. The vertex cover number is
τ(G)=min⁡{∣C∣:C is a vertex cover of G}.\tau(G) = \min\{|C| : C \text{ is a vertex cover of } G\}.
  • An independent set is a set I⊆VI \subseteq V such that no edge of GG has both endpoints in II. The independence number is
α(G)=max⁡{∣I∣:I is an independent set of G}.\alpha(G) = \max\{|I| : I \text{ is an independent set of } G\}.
  • A matching is a set M⊆EM \subseteq E of pairwise disjoint edges (no two share an endpoint). The matching number is
ν(G)=max⁡{∣M∣:M is a matching of G}.\nu(G) = \max\{|M| : M \text{ is a matching of } G\}.
  • A vertex is saturated (or covered) by a matching MM if it is an endpoint of some edge in MM; otherwise it is exposed.
  • GG is bipartite if VV admits a partition V=X⊔YV = X \sqcup Y such that every edge has one endpoint in XX and one in YY.

Note CC is a vertex cover of GG if and only if V∖CV \setminus C is an independent set, since an edge avoids CC exactly when both its endpoints lie in V∖CV\setminus C. Consequently

τ(G)+α(G)=∣V(G)∣\tau(G) + \alpha(G) = |V(G)|

for every graph GG; this identity is sometimes called the Gallai identity and holds with no bipartiteness assumption.

Intuition

Think of XX as a set of workers and YY as a set of tasks, with an edge xyxy meaning worker xx is qualified for task yy. A matching assigns qualified workers to distinct tasks with no conflicts. A vertex cover is a "watchlist": a set of workers and tasks such that every qualification (edge) involves someone on the list, meaning the list is enough to certify or veto every possible assignment. Why should the largest conflict-free assignment (ν\nu) equal the smallest watchlist (τ\tau)? One direction is easy and holds in every graph, bipartite or not: any vertex cover must contain at least one endpoint of each matching edge, and since matching edges are pairwise disjoint, no vertex can serve double duty, forcing ∣C∣≥∣M∣|C| \ge |M| for any matching MM and cover CC. Hence τ(G)≥ν(G)\tau(G) \ge \nu(G) always. The surprising content of König's theorem is the reverse inequality in the bipartite case: you can always find a cover no larger than the maximum matching. The bipartite structure is what makes this possible — it lets us organize the "slack" vertices (those left exposed by a maximum matching) into alternating paths that never loop back on themselves, a phenomenon that fails once odd cycles are present.

Figure
A bipartite graph with a maximum matching (bold) and a minimum vertex cover (circled), both of size 3
x1 x2 x3 x4 y1 y2 y3 bold = maximum matching M (|M|=3); red circles = minimum vertex cover {y1, y2, x3} (size 3)

Alternating paths and augmenting paths

Fix a matching MM in a graph GG. A path is MM-alternating if its edges alternate between edges in MM and edges not in MM. An MM-augmenting path is an MM-alternating path whose two endpoints are both exposed by MM. The name is justified by the following standard fact, which we record as a lemma since the proof of König's theorem uses it.

LemmaAugmenting path lemma

Let MM be a matching in a graph GG. Then MM is a maximum matching if and only if GG contains no MM-augmenting path.

Proof

(⇒\Rightarrow) Suppose MM is maximum but, for contradiction, PP is an MM-augmenting path with edge set E(P)E(P). Since PP alternates starting and ending with non-matching edges (both endpoints exposed), PP has one more non-matching edge than matching edge. Let

M′=M △ E(P)=(M∖E(P))∪(E(P)∖M),M' = M \,\triangle\, E(P) = (M \setminus E(P)) \cup (E(P)\setminus M),

the symmetric difference. Every vertex of GG not on PP has the same matching status in M′M' as in MM, since M′M' only changes edges within PP. Along PP, replacing matching edges with non-matching edges and vice versa yields a valid matching on PP (each internal vertex of PP is incident to exactly one matching edge and one non-matching edge of PP, so swapping preserves the disjointness condition), and ∣M′∣=∣M∣+1|M'| = |M| + 1. This contradicts maximality of MM. (⇐\Leftarrow) Suppose GG has no MM-augmenting path; we show MM is maximum. Let M∗M^* be any maximum matching and consider H=M△M∗H = M \triangle M^* as a subgraph of GG (edge set only, ignoring isolated vertices). In HH, every vertex has degree at most 22, since it is incident to at most one edge of MM and at most one edge of M∗M^*. Hence every connected component of HH is either an isolated vertex, a path, or a cycle, and edges alternate between MM and M∗M^* along any such path or cycle (since HH's edges alternately came from M∖M∗M \setminus M^* and M∗∖MM^*\setminus M, and two consecutive edges at a vertex cannot both belong to the same matching). Cycles in HH must have even length and contain equally many MM-edges and M∗M^*-edges. Consider a path component PP of HH. If PP had strictly more M∗M^*-edges than MM-edges, then PP would be MM-alternating with both endpoints exposed by MM (an endpoint of PP meets only one edge of HH; if that edge belongs to M∗M^*, the endpoint is not covered by MM-edges of PP, and having more M∗M^*-edges than MM-edges forces both ends to be of this type) — i.e. PP would be an MM-augmenting path in GG, contradicting our hypothesis. So every path component of HH has at most as many M∗M^*-edges as MM-edges. Summing over all components (cycles contribute equally to both, path components contribute at least as many MM-edges as M∗M^*-edges),

∣M∗∣=∣M∗∩H∣+∣M∗∖H∣≤∣M∩H∣+∣M∖H∣=∣M∣,|M^*| = |M^* \cap H| + |M^*\setminus H| \le |M \cap H| + |M \setminus H| = |M|,

using that edges outside HH are common to both matchings. Combined with ∣M∣≤∣M∗∣|M| \le |M^*| (maximality of M∗M^*), we get ∣M∣=∣M∗∣|M|=|M^*|, so MM is maximum.

∎

This lemma is the standard engine behind matching algorithms and behind the proof of König's theorem given below; it is exactly the bipartite-graph statement dual to Hall's Theorem, which characterizes when a perfect matching saturating one side exists.

TheoremKönig's Theorem

Let G=(X⊔Y,E)G = (X \sqcup Y, E) be a finite bipartite graph. Then

ν(G)=τ(G),\nu(G) = \tau(G),

that is, the maximum size of a matching equals the minimum size of a vertex cover.

Proof

We give a constructive proof, building an explicit vertex cover of size ν(G)\nu(G) from a maximum matching, using alternating paths. The technique is the classical König–Egerváry alternating-path construction.

Step 1: The easy inequality ν(G)≤τ(G)\nu(G) \le \tau(G), valid in any graph. Let MM be any matching and CC any vertex cover. Each edge e∈Me \in M has at least one endpoint in CC (since CC is a vertex cover); define f:M→Cf: M \to C by letting f(e)f(e) be such an endpoint (choose one if both qualify). If e1≠e2e_1 \ne e_2 are distinct edges of MM, they are disjoint (matching property), so f(e1)≠f(e2)f(e_1) \ne f(e_2). Thus ff is injective, giving ∣M∣≤∣C∣|M| \le |C|. Taking MM maximum and CC minimum yields ν(G)≤τ(G)\nu(G) \le \tau(G).

Step 2: Construction of a cover of size ν(G)\nu(G) (uses bipartiteness). Let MM be a maximum matching in GG, with ∣M∣=ν(G)|M| = \nu(G). Let U⊆XU \subseteq X be the set of vertices in XX exposed (unmatched) by MM. Define ZZ to be the set of all vertices reachable from UU by MM-alternating paths (paths starting at a vertex of UU alternating between non-matching and matching edges; U⊆ZU \subseteq Z trivially via the empty path). Let

ZX=Z∩X,ZY=Z∩Y.Z_X = Z \cap X, \qquad Z_Y = Z \cap Y.

Define

C=(X∖ZX)∪ZY.C = (X \setminus Z_X) \cup Z_Y.

We claim CC is a vertex cover of GG with ∣C∣=ν(G)|C| = \nu(G).

Claim A: CC is a vertex cover. Let e=xye = xy be any edge with x∈Xx \in X, y∈Yy \in Y. Suppose for contradiction that ee is not covered by CC, i.e. x∉Cx \notin C and y∉Cy \notin C. Since x∉X∖ZXx \notin X\setminus Z_X, we get x∈ZXx \in Z_X, i.e. xx is reachable from UU by an alternating path. Since y∉ZYy \notin Z_Y, yy is not reachable from UU by an alternating path. Case (i): e∈Me \in M. Then since x∈ZXx \in Z_X is reached by some alternating path PP ending at xx, and e=xy∈Me=xy \in M, either PP already uses ee to arrive having come from yy (impossible, since then yy would already be on the path, hence reachable, contradicting y∉ZYy \notin Z_Y), or PP does not use ee. If PP does not use edge ee, consider extending PP by traversing ee from xx to yy: since e∈Me \in M and the alternating path must reach xx via a non-matching edge or be trivial (x∈Ux \in U), appending the matching edge xyxy keeps the alternation valid (arriving at xx via non-M-edge or as start point, then leaving via M-edge xyxy) provided xx's matching partner is exactly yy (true here since e=xy∈Me = xy \in M and MM is a matching, so xx has a unique partner). Hence PP extended by ee is a valid alternating path reaching yy, so y∈ZYy \in Z_Y, a contradiction. Case (ii): e∉Me \notin M. Since x∈ZXx \in Z_X, either x∈Ux \in U or xx is reached via a matching edge into xx. If x∈Ux \in U (exposed), then the single edge xy∉Mxy \notin M is itself a valid alternating path from UU to yy (a path of length one using a non-matching edge starting at an exposed vertex is alternating by definition), so y∈ZYy \in Z_Y: contradiction. If x∉Ux \notin U, then xx is matched by some edge e′=xy′∈Me' = x y' \in M with y′≠yy' \ne y (since e∉Me \notin M, xx's matching partner is not yy), and xx is reached along its alternating path PP via the matching edge e′e' (arriving at xx from y′y'). Extend PP by the non-matching edge xyxy: since the edge into xx was a matching edge, alternation requires the next edge from xx to be a non-matching edge, and xy∉Mxy \notin M satisfies this. So yy is reachable, y∈ZYy \in Z_Y: contradiction. In both cases we reach a contradiction, so no edge avoids CC. Hence CC is a vertex cover. ■\blacksquare (Claim A)

Claim B: ∣C∣=∣M∣|C| = |M|, hence ∣C∣=ν(G)|C| = \nu(G). First, no vertex of UU lies in ZYZ_Y's "reach" as an X-vertex needing to be matched incorrectly — more precisely we show: (i) Every vertex of ZYZ_Y is matched by MM to a vertex of ZXZ_X. (ii) Every vertex of X∖ZXX \setminus Z_X is matched by MM (i.e., X∖ZXX\setminus Z_X contains no exposed vertex). (iii) The matching MM restricted to edges between ZYZ_Y and ZXZ_X is a perfect matching between these two sets, and C=(X∖ZX)∪ZYC = (X\setminus Z_X)\cup Z_Y consists precisely of one endpoint from each edge of a specific sub-matching plus all of X∖ZXX \setminus Z_X, giving ∣C∣=∣M∣|C| = |M| exactly. Proof of (ii): every vertex of UU is, by definition, in XX and reachable from itself (trivial path), so U⊆ZXU \subseteq Z_X, hence X∖ZXX \setminus Z_X contains no vertex of UU; since UU is exactly the exposed vertices of XX, every vertex in X∖ZXX\setminus Z_X is matched. Proof of (i): let y∈ZYy \in Z_Y, reached by an alternating path PP from some u∈Uu \in U. Since PP ends at y∈Yy \in Y and starts at u∈Xu \in X, and alternates, the path has odd length, and by the alternation rule (starting with a non-matching edge, since uu is exposed so the first edge from uu cannot be a matching edge) the last edge of PP (arriving at yy) is a matching edge. [If PP has length 11: it is a single non-matching edge from uu to yy — but then the last edge is non-matching, contradicting what we need. We resolve this by checking yy must actually be matched: if yy were exposed, the single edge uy∉Muy \notin M together with uu exposed and yy exposed would make uyuy itself an MM-augmenting path, contradicting maximality of MM by the Augmenting path lemma. So yy is matched, and by induction on path length one shows the edge of MM at yy is the last edge of the shortest alternating path reaching yy, landing back in ZXZ_X.] In general, since MM is maximum, by the augmenting path lemma ZZ contains no exposed vertex of YY (else that vertex together with its reaching path would be an augmenting path), so every y∈ZYy \in Z_Y is matched by some edge of MM; that edge must go to a vertex of ZXZ_X, because the matching edge at yy, prepended to the alternating path reaching yy, extends the alternating reachability to yy's partner (arriving at yy via a non-matching edge forces leaving via the matching edge to stay alternating, and this reaches the partner, which is therefore in ZXZ_X). So MM restricts to a matching M0M_0 between ZYZ_Y and ZXZ_X that saturates all of ZYZ_Y (by (i)) and, combined with (ii), every vertex of X∖ZXX\setminus Z_X is matched by some edge of MM landing in YY; we must check that edge does not land in ZYZ_Y — if x∈X∖ZXx \in X\setminus Z_X were matched to y′∈ZYy'\in Z_Y, then since y′∈ZYy' \in Z_Y is reached by an alternating path ending with the matching edge xy′x y' (by the argument above, the matching partner of any y∈ZYy\in Z_Y lies in ZXZ_X), we'd conclude x∈ZXx \in Z_X, contradicting x∈X∖ZXx \in X \setminus Z_X. So every vertex of X∖ZXX \setminus Z_X is matched to a vertex of Y∖ZYY \setminus Z_Y. Therefore MM splits into two parts: a perfect matching M0M_0 between ZYZ_Y and ZXZ_X (by (i), every ZYZ_Y-vertex is matched into ZXZ_X; and conversely every matched vertex of ZX∖UZ_X \setminus U arises this way since U⊆ZXU \subseteq Z_X consists of exposed vertices not involved in M0M_0 from this side — precisely, M0M_0 matches ZYZ_Y bijectively into ZX∖UZ_X \setminus U), and a matching M1M_1 between X∖ZXX\setminus Z_X and Y∖ZYY \setminus Z_Y saturating all of X∖ZXX \setminus Z_X. Since M=M0∪M1M = M_0 \cup M_1 (disjoint union, as they involve disjoint vertex sets on each side) and U⊆ZXU\subseteq Z_X is unmatched,

∣M∣=∣M0∣+∣M1∣=∣ZY∣+∣X∖ZX∣=∣C∣.|M| = |M_0| + |M_1| = |Z_Y| + |X\setminus Z_X| = |C|.

Here ∣M0∣=∣ZY∣|M_0| = |Z_Y| because M0M_0 saturates ZYZ_Y bijectively into a subset of ZXZ_X, and ∣M1∣=∣X∖ZX∣|M_1| = |X \setminus Z_X| because M1M_1 saturates all of X∖ZXX\setminus Z_X. This proves ∣C∣=∣M∣=ν(G)|C| = |M| = \nu(G). ■\blacksquare (Claim B)

Conclusion. Combining Claims A and B, CC is a vertex cover with ∣C∣=ν(G)|C| = \nu(G), so

τ(G)≤∣C∣=ν(G).\tau(G) \le |C| = \nu(G).

Together with Step 1's inequality ν(G)≤τ(G)\nu(G) \le \tau(G), we conclude ν(G)=τ(G)\nu(G) = \tau(G). ■\blacksquare

∎

Worked examples

Example 1: an asymmetric bipartite graph. Let X={x1,x2,x3,x4}X = \{x_1,x_2,x_3,x_4\}, Y={y1,y2,y3}Y=\{y_1,y_2,y_3\}, with edges

E={x1y1, x1y2, x2y1, x3y2, x3y3, x4y1}.E = \{x_1y_1,\ x_1y_2,\ x_2y_1,\ x_3y_2,\ x_3y_3,\ x_4y_1\}.

Note ∣X∣=4>∣Y∣=3|X| = 4 > |Y| = 3, so no matching can saturate XX; also x2x_2 and x4x_4 are both only adjacent to y1y_1. Finding a maximum matching. Try M={x1y2, x2y1, x3y3}M = \{x_1y_2,\ x_2y_1,\ x_3y_3\}. Check disjointness: endpoints used are x1,x2,x3,y1,y2,y3x_1,x_2,x_3,y_1,y_2,y_3, all distinct, so MM is a valid matching of size 33. Is MM maximum? Since ∣Y∣=3|Y|=3, no matching can exceed size 33 (each matching edge needs a distinct YY-endpoint), so ν(G)≤3\nu(G) \le 3, and we exhibited a matching of size 33, giving ν(G)=3\nu(G) = 3. Constructing the cover via the proof's algorithm. The only exposed vertex in XX is x4x_4 (all others are matched by MM), so U={x4}U = \{x_4\}. Find alternating paths from x4x_4: the edges at x4x_4 are just x4y1x_4y_1 (non-matching, since x4x_4 is unmatched). This reaches y1y_1. From y1y_1, the matching edge is x2y1x_2y_1, so we reach x2x_2. From x2x_2, the only edge is x2y1x_2y_1 (already used), so the alternating exploration from x2x_2 ends (no other edges at x2x_2). So

Z={x4,y1,x2},ZX={x4,x2},ZY={y1}.Z = \{x_4, y_1, x_2\}, \quad Z_X = \{x_4,x_2\}, \quad Z_Y = \{y_1\}.

The theorem's cover is

C=(X∖ZX)∪ZY={x1,x3}∪{y1}={x1,x3,y1}.C = (X\setminus Z_X)\cup Z_Y = \{x_1,x_3\}\cup\{y_1\} = \{x_1, x_3, y_1\}.

Verify CC is a vertex cover: check all six edges. x1y1x_1y_1: contains x1∈Cx_1\in C. x1y2x_1y_2: contains x1x_1. x2y1x_2y_1: contains y1y_1. x3y2x_3y_2: contains x3x_3. x3y3x_3y_3: contains x3x_3. x4y1x_4y_1: contains y1y_1. All six edges are covered, and ∣C∣=3=ν(G)|C|=3=\nu(G), matching the theorem's guarantee exactly. No cover of size 22 can exist since that would force τ(G)<ν(G)\tau(G) < \nu(G), violating Step 1's inequality — consistent with König's theorem.

Example 2: using König's theorem to certify a maximum matching, and cross-checking with Hall's theorem. Let X={a,b,c,d}X = \{a,b,c,d\}, Y={p,q,r,s}Y = \{p,q,r,s\} with edges

E={ap, aq, bp, br, cs, dp, dq, dr}.E = \{ap,\ aq,\ bp,\ br,\ cs,\ dp,\ dq,\ dr\}.

Consider the matching M={aq, br, cs}M = \{aq,\ br,\ cs\}, of size 33. Vertex dd is exposed, and pp is exposed (unused by MM). Is MM maximum, or can we augment? Look for an MM-augmenting path starting at exposed vertex dd. Edges at dd: dp,dq,drdp, dq, dr — all non-matching (good, valid start). Try d→pd \to p: pp is exposed! So dd–pp is itself an augmenting path of length 11 (both endpoints exposed, single non-matching edge). By the Augmenting path lemma, MM is not maximum. Augment: remove nothing, add dpdp, giving

M′={aq, br, cs, dp},∣M′∣=4.M' = \{aq,\ br,\ cs,\ dp\}, \quad |M'| = 4.

Since ∣X∣=4|X| = 4, this saturates all of XX, so M′M' is a maximum matching: ν(G)=4\nu(G) = 4. Cross-check with König's theorem: τ(G)\tau(G) must also equal 44. Exhibit a cover of size 44: since M′M' saturates XX, take C=X={a,b,c,d}C = X = \{a,b,c,d\} itself. Every edge has an XX-endpoint (bipartite structure), so C=XC=X is automatically a vertex cover, of size 4=ν(G)=τ(G)4=\nu(G)=\tau(G) by König's theorem — no smaller cover is possible. Cross-check with Hall's theorem: since M′M' saturates XX, Hall's condition ∣N(S)∣≥∣S∣|N(S)|\ge |S| must hold for every S⊆XS\subseteq X. Check the tightest case S={a,d}S = \{a,d\}: N(a)={p,q}N(a)=\{p,q\}, N(d)={p,q,r}N(d) = \{p,q,r\}, so N(S)={p,q,r}N(S) = \{p,q,r\}, size 3≥23 \ge 2. Check S=XS = X: N(X)={p,q,r,s}=YN(X) = \{p,q,r,s\} = Y, size 4≥44 \ge 4, tight — consistent with XX being fully saturated and ∣X∣=∣Y∣|X|=|Y|.

CounterexampleBipartiteness is necessary — the triangle

Let G=K3G = K_3, the complete graph on three vertices {u,v,w}\{u,v,w\} with all three edges uv,vw,uwuv, vw, uw present. This graph is not bipartite (it contains an odd cycle, itself). Matching number: any two edges of K3K_3 share a vertex (there are only 33 vertices total), so no two edges are disjoint; hence the maximum matching has size ν(G)=1\nu(G) = 1. Vertex cover number: a single vertex, say uu, covers edges uvuv and uwuw but not vwvw (which touches neither uu endpoint). So no single vertex is a cover. Two vertices, say {u,v}\{u,v\}, cover uvuv (both endpoints), uwuw (endpoint uu), and vwvw (endpoint vv) — all three edges. So τ(G)≤2\tau(G) \le 2, and since τ(G)=1\tau(G)=1 is impossible (just shown), τ(G)=2\tau(G) = 2. Hence ν(G)=1<2=τ(G)\nu(G) = 1 < 2 = \tau(G): the min-max equality fails. The reason traces exactly to the proof: the alternating-path construction in Step 2 crucially used the two-coloring X,YX,Y to consistently classify "arriving via a matching edge" versus "arriving via a non-matching edge" without contradiction. In an odd cycle, an alternating walk can return to a vertex having traversed an odd number of edges, breaking the clean bipartition C=(X∖ZX)∪ZYC = (X\setminus Z_X)\cup Z_Y into a cover of the right size — indeed here the analogous construction would try to use vertex vv (reached from the "exposed" side) but the odd triangle forces an extra vertex into the cover. This single example is exactly why the general (non-bipartite) theory requires the more intricate Tutte–Berge formula, which correctly accounts for the "blossoms" (odd components) that a triangle exemplifies.

Scope, edge cases & common traps

SituationWhat holdsCaution
GG bipartiteν(G)=τ(G)\nu(G) = \tau(G) (König)Requires a genuine 2-coloring; check for odd cycles first
GG general (possibly non-bipartite)Only ν(G)≤τ(G)\nu(G) \le \tau(G)Equality can fail, e.g. K3K_3, K5K_5, any odd cycle C2k+1C_{2k+1}
GG bipartite, disconnectedKönig still applies (apply to each component, sum)Do not forget isolated vertices need no coverage
Weighted / fractional relaxationsLP duality gives τ∗(G)=ν∗(G)\tau^*(G) = \nu^*(G) for the fractional versions in any graphFractional equality is easier and always true; König is its integral, bipartite-exact refinement
Finding τ(G)\tau(G) algorithmicallyCompute a maximum matching (e.g. via augmenting paths / Hopcroft–Karp), then run the ZZ-constructionThe construction needs the specific maximum matching, not an arbitrary one

The mathematician behind it

Origins · 1 minDénes Kőnig and how this was discovered
DK
Dénes Kőnig
1884–1944 · Budapest, Hungary

Kőnig was a Hungarian mathematician and one of the founders of modern graph theory as a systematic discipline, writing the first comprehensive graph theory textbook, Theorie der endlichen und unendlichen Graphen (1936). He worked at the Budapest University of Technology and made foundational contributions connecting combinatorics to matrix theory, most famously the min-max theorem on bipartite graphs that bears his name, obtained around the same time as an equivalent result by his colleague Jenő Egerváry on doubly stochastic matrices and the assignment problem. Kőnig's work laid direct groundwork for what became combinatorial optimization and, later, network flow theory.

History
- 1884: Dénes Kőnig born in Budapest, son of mathematician Gyula Kőnig.
- 1916: Kőnig proves an early edge-coloring / matching result for bipartite graphs, part of the lineage leading to his theorem.
- 1931: Kőnig publishes the min-max theorem equating maximum matching and minimum vertex cover in bipartite graphs; Egerváry independently proves an equivalent weighted version the same year.
- 1936: Kőnig publishes the first systematic graph theory textbook, cementing the field's terminology and core theorems.
- 1944: Kőnig dies in Budapest; his theorem becomes a cornerstone result cited in essentially every subsequent treatment of matching theory and combinatorial optimization.
Does König's theorem hold for directed or weighted graphs?

The classical statement is for finite, simple, undirected, unweighted bipartite graphs, and that is the version proved here. There are important generalizations: the weighted version (relating maximum weight matchings to minimum weight vertex covers under LP relaxations) underlies the assignment problem and Egerváry's original work, and is solved algorithmically by the Hungarian algorithm. Directed graph analogues exist via reductions to flow networks — replacing each edge with directed arcs and adding a source/sink turns the bipartite matching problem into a max-flow problem, and König's theorem becomes a special case of max-flow min-cut with unit capacities. The core combinatorial statement, however, is inherently about undirected bipartite structure.

How does König's theorem relate to Hall's theorem?

Hall's theorem characterizes exactly when a bipartite graph G=(X⊔Y,E)G=(X\sqcup Y,E) has a matching saturating XX: this happens if and only if ∣N(S)∣≥∣S∣|N(S)| \ge |S| for every S⊆XS \subseteq X. König's theorem is a strict generalization in spirit: it computes ν(G)\nu(G) even when no such saturating matching exists, via the dual quantity τ(G)\tau(G). In fact, one classical proof strategy derives König's theorem from a deficiency version of Hall's theorem (Hall–König deficiency formula), which states ν(G)=∣X∣−max⁡S⊆X(∣S∣−∣N(S)∣)\nu(G) = |X| - \max_{S\subseteq X}(|S| - |N(S)|). The proof given in this article is self-contained and does not require Hall's theorem, using alternating paths directly, but the two results are tightly interlinked as complementary facets of bipartite matching theory.

Is finding a minimum vertex cover still hard for non-bipartite graphs?

Yes — for general graphs, computing τ(G)\tau(G) (equivalently α(G)\alpha(G), via the Gallai identity τ+α=∣V∣\tau+\alpha=|V|) is one of Karp's 21 NP-complete problems, meaning no polynomial-time algorithm is known (and none is believed to exist) unless P = NP. The bipartite case is a genuine exception where the min-max duality collapses the two hard problems (max matching, and equivalently min cover) into a single tractable one, since maximum matchings in bipartite graphs are computable in polynomial time (e.g., via the Hopcroft–Karp algorithm in O(EV)O(E\sqrt V) time). This makes bipartite vertex cover one of the few nontrivial polynomial special cases of an otherwise NP-hard family of problems.

Can the minimum vertex cover be found directly, without first finding a maximum matching?

In principle yes, but the standard and most efficient method is exactly the one in this article's proof: compute a maximum matching MM first (efficiently, via augmenting paths), then perform the alternating-path reachability computation from exposed XX-vertices to identify ZZ, and output C=(X∖ZX)∪ZYC = (X\setminus Z_X)\cup Z_Y. This two-phase algorithm runs in time dominated by the matching computation, i.e. polynomial time overall. There is no known method that computes the minimum cover meaningfully faster without implicitly solving a matching problem, since the two quantities are provably equal and matching is the more structurally tractable of the two to compute directly.

What happens if the bipartite graph has isolated vertices or is disconnected?

Isolated vertices (degree 00) never need to be in a minimum vertex cover, since they touch no edges, and they never help build a matching; the theorem's statement and proof are unaffected — such vertices simply do not appear in UU, ZZ, or any minimal cover. For disconnected bipartite graphs, apply König's theorem separately to each connected component (each component is itself bipartite, inheriting the 2-coloring), then sum: both ν(G)\nu(G) and τ(G)\tau(G) decompose additively over components, since matchings and covers in different components do not interact, so the min-max equality holds component-wise and hence globally.

Does König's theorem give an algorithm to find a maximum independent set in bipartite graphs too?

Yes, immediately via the Gallai identity α(G)+τ(G)=∣V(G)∣\alpha(G) + \tau(G) = |V(G)|, which holds in every graph (bipartite or not) because a set is independent exactly when its complement is a vertex cover. Combining this with König's theorem gives, for bipartite GG,

α(G)=∣V(G)∣−ν(G),\alpha(G) = |V(G)| - \nu(G),

so a maximum independent set in a bipartite graph can be computed in polynomial time by first finding a maximum matching and then taking the complement of the resulting minimum vertex cover. This is notable because maximum independent set is NP-hard on general graphs, making bipartite graphs another rare tractable exception, directly powered by König's theorem.

Before this

Where this leads