The König-Egerváry Identity for Bipartite Graphs

From Matchings and Covers to Independent Sets

In a bipartite graph, three different ways of selecting vertices or edges are tied together: a largest independent set, a largest matching, and a smallest vertex cover. The identity in this tutorial expresses that connection using only the independent-set and matching numbers. Its proof has two parts: first relate independent sets to vertex covers in every graph; then use Kőnig’s matching-cover theorem, which applies to bipartite graphs.

All graphs in this tutorial are finite and simple. A set $S\subseteq V(G)$ is independent if no two vertices in $S$ are adjacent. A vertex cover is a set $C\subseteq V(G)$ containing at least one endpoint of every edge. A matching is a set of edges no two of which share an endpoint. The independence number $\alpha(G)$ is the largest size of an independent set, and the matching number $\nu(G)$ is the largest size of a matching. The vertex cover number $\tau(G)$ is the smallest size of a vertex cover.

Theorem (Kőnig-Egerváry identity): If $G$ is a finite bipartite graph, then $$ \alpha(G)+\nu(G)=|V(G)|. $$

The conclusion concerns maximum sizes: $\alpha(G)$ is not the size of an arbitrary independent set, and $\nu(G)$ is not the size of an arbitrary matching. Bipartite means that $V(G)$ has a partition into two sets such that every edge has one endpoint in each set.

Complements Turn Independent Sets into Covers

Lemma: For any finite graph $G$, a set $S\subseteq V(G)$ is independent if and only if $V(G)\setminus S$ is a vertex cover. Consequently, $$ \alpha(G)+\tau(G)=|V(G)|. $$

Proof. Suppose first that $S$ is independent. If an edge had both endpoints outside $V(G)\setminus S$, then both endpoints would belong to $S$, contradicting independence. Thus every edge has an endpoint in $V(G)\setminus S$, so that complement is a vertex cover. Conversely, suppose $V(G)\setminus S$ is a vertex cover. If an edge had both endpoints in $S$, neither endpoint would lie in the cover, contradicting the definition of a cover. Hence $S$ is independent.

Taking complements is a bijection between independent sets and vertex covers: applying the complement operation twice returns the original set. If $n=|V(G)|$, then the complement of a set of size $s$ has size $n-s$. Therefore the largest independent-set size is $n$ minus the smallest vertex-cover size, giving $\alpha(G)=n-\tau(G)$, or $\alpha(G)+\tau(G)=n$. This argument also includes the graph with no vertices: its only subset is the empty set, which is both independent and a cover, and both parameters are zero. $\square$

For bipartite graphs, Kőnig’s matching-cover theorem states that $\tau(G)=\nu(G)$. This theorem was established in the earlier material on Kőnig’s matching-cover theorem. Its hypotheses matter: it equates the minimum vertex-cover size and maximum matching size for a finite bipartite graph. Combining it with the lemma gives the identity.

Proof of the Kőnig-Egerváry identity. Let $G$ be a finite bipartite graph, and write $n=|V(G)|$. The complement lemma gives $\alpha(G)+\tau(G)=n$. By Kőnig’s matching-cover theorem, $\tau(G)=\nu(G)$. Substitution yields $\alpha(G)+\nu(G)=n$, as claimed. $\square$

Worked Examples

Worked Example: A Path on Five Vertices

Let $G$ have $V(G)=\{1,2,3,4,5\}$ and $E(G)=\{12,23,34,45\}$. This is the path $P_5$, and it is bipartite with parts $\{1,3,5\}$ and $\{2,4\}$.

The set $\{1,3,5\}$ is independent: none of its vertices are consecutive along the path. To verify it is largest, partition the vertices into the adjacent pairs $\{1,2\}$, $\{3,4\}$, and the singleton $\{5\}$. An independent set can include at most one vertex from each pair and at most the one singleton. Its size is therefore at most $1+1+1=3$. Hence $\alpha(G)=3$.

The edges $12$ and $34$ form a matching of size $2$. No matching can have more than $\lfloor 5/2\rfloor=2$ edges, since each matching edge uses two distinct vertices. Thus $\nu(G)=2$. Substituting the values gives $\alpha(G)+\nu(G)=3+2=5=|V(G)|$.

Check: The bipartition is valid because each listed edge joins one vertex from $\{1,3,5\}$ to one from $\{2,4\}$. The computed independent-set and matching sizes sum to the graph’s order.

Worked Example: A Complete Bipartite Graph

Let $G=K_{2,3}$, with parts $X=\{a,b\}$ and $Y=\{1,2,3\}$. Explicitly, $V(G)=\{a,b,1,2,3\}$ and $E(G)=\{a1,a2,a3,b1,b2,b3\}$.

The set $Y$ is independent, so $\alpha(G)\ge 3$. If an independent set contains any vertex of $X$, it can contain no vertex of $Y$, because every vertex of $X$ is adjacent to every vertex of $Y$. Such a set has size at most $2$. If it contains no vertex of $X$, it is a subset of $Y$ and has size at most $3$. Therefore $\alpha(G)=3$.

The edges $a1$ and $b2$ form a matching of size $2$. Every matching uses a distinct vertex of $X$ for each of its edges, and $X$ has only two vertices, so no matching has size above $2$. Thus $\nu(G)=2$, and $\alpha(G)+\nu(G)=3+2=5=|V(G)|$.

Check: The graph has $2\cdot3=6$ edges, exactly the six listed. Its matching uses two different vertices in each part, and its independent set uses all three vertices of $Y$.

Worked Example: Components and an Isolated Vertex

Let $G$ have $V(G)=\{a,b,c,d,e,f\}$ and $E(G)=\{ab,bc,de\}$. Its components are the path $a,b,c$, the edge $de$, and the isolated vertex $f$. One bipartition is $X=\{a,c,d,f\}$, $Y=\{b,e\}$; each of the three edges crosses between the parts.

Within the path component, $\{a,c\}$ is independent and no independent set can contain all three vertices, because $ab$ and $bc$ are edges. Its maximum independent-set size is $2$. Within the edge component, at most one endpoint can be selected, giving maximum size $1$. The isolated vertex $f$ can always be included, contributing $1$. Since there are no edges between components, the choices combine: $\alpha(G)=2+1+1=4$.

A matching can use at most one edge from the path component, at most one from the edge component, and none from the isolated vertex. The matching $\{ab,de\}$ attains this bound, so $\nu(G)=1+1=2$. Thus $\alpha(G)+\nu(G)=4+2=6=|V(G)|$. The isolated vertex contributes to the independent set and to the vertex count, but not to the matching.

Check: The three components have orders $3$, $2$, and $1$, whose sum is $6$. Their computed contributions to $\alpha$ sum to $4$, and their matching contributions sum to $2$.

Why Bipartiteness Is Essential

The complement lemma holds for every graph, but replacing $\tau(G)$ with $\nu(G)$ requires bipartiteness. Outside that setting, a minimum vertex cover can be larger than a maximum matching. For example, let $G$ be the triangle with $V(G)=\{1,2,3\}$ and $E(G)=\{12,23,31\}$. It has no independent set of size $2$, so $\alpha(G)=1$. A matching has at most one edge because every two edges of the triangle share a vertex, and one edge is a matching, so $\nu(G)=1$. Hence $\alpha(G)+\nu(G)=1+1=2$, while $|V(G)|=3$. This graph is not bipartite: its three edges form an odd cycle.

A useful way to read the identity is that, in a bipartite graph, a smallest cover and a largest matching have the same size. The complement of a smallest cover is a largest independent set, so its size is $n-\nu(G)$. This explains both the formula and why the identity does not say that every independent set and every matching have sizes summing to $n$.

Common Pitfalls

Using arbitrary sets instead of extremal sizes. In $P_5$, the independent set $\{1,3\}$ has size $2$, while the matching $\{12\}$ has size $1$; their sizes sum to $3$, not $5$. The identity uses $\alpha(G)=3$ and $\nu(G)=2$, the maximum possible sizes.

Applying the identity to every graph. The triangle calculation gives $2\neq3$. The complement relation still holds there, but Kőnig’s matching-cover theorem does not apply, because the triangle is not bipartite.

Forgetting isolated vertices. An isolated vertex belongs to a maximum independent set and cannot belong to any matching edge. It still counts toward $n$; omitting it from the vertex count breaks the identity.

Check Your Understanding

Use the complement relation and the bipartite hypothesis carefully in each question.

For $P_6$, determine $\alpha(G)$ and $\nu(G)$, and verify their sum equals the order.
Prove that adding one isolated vertex to a bipartite graph increases $\alpha(G)$ and $|V(G)|$ by one while leaving $\nu(G)$ unchanged.
For $K_{1,4}$, find a maximum independent set and a maximum matching, and check the identity.
Explain why the complement of a minimum vertex cover is a maximum independent set.
For the triangle, compute $\tau(G)$ as well as $\alpha(G)$ and $\nu(G)$. Which equality in the bipartite argument fails?