Kőnig-Egerváry theorem

Graph theory has been my most favourite thing to learn in maths and and in this blog i hope to spread the knowledge about Kőnig's theorem. It is advised that the readers are aware about basic graph theory terminologies including bipartite graphs.

Before going on to the theorem i would like to go on about matchings and vertex cover which we are going to use in the theorem 

Matchings

A matching $M$ of a graph $G$ is a subset of the edges of a graph in which no two edge share a common vertex (non adjacent edges). For example :-

The Matching $M$ over here is edge $\{ 3 - 5 , 1-2 , \}$ or $\{ 1 - 2 , 4 - 3 \}$ etc . 

Maximum Matching is a matching that contains the largest possible number of edges for instance in the above example the maximum matching is 2 edges as there cannot be a subset of non adjacent edges having greater than 2 edges (Readers are advised to try so they can convince themselves)

A Perfect Matching is a matching that matches all vertices of the graph or in other sense it is a matching in which all vertices of the graph is covered . (Can you see what can be a perfect matching in the above example) 

Vertex Cover

Vertex Cover of a graph is a set of vertices that includes atleast one end point of every edge in the graph (set of vertices which includes all the edges where atleast one of the edge point is included in the set). 

Sounds a bit scary, no problem!! Let's look at the same example above again. It can clearly be seen that  $\{1,3 \} $ is a vertex cover as the vertices $\{1,3\}$ covers all the edges or altealst one edge point of every edge is connected to $1$ or $3$ in a way , similarly $\{1,2,4,5\}$ is also a vertex cover. Try finding more vertex cover in that example 

A Minimum Vertex Cover is a vertex cover that consists the least number of vertices covering all the edges or that includes atleast one end point of every edge in the graph. Try figuring out the minimum vertex cover in the previous example.

Now we can talk about the main part of this blog or known as Kőnig-Egerváry theorem

Kőnig-Egerváry theorem

The statement of Kőnig-Egerváry theorem  says that the number of edges in a maximum matching equals the number of vertices in a minimum vertex cover in any bipartite graph 

So lets say we have a bipartite graph $G$ and the maximum matching consists of $E$ number of edges and the minimum vertex cover has $V$ vertices , the theorem says $E = V$

Proof :

Now its clear that no vertex in a vertex cover can cover more than one edge of $M$ from their definition  where $M$ is a maximum matching of a bipartite graph $G = (V,E) $ (the edge half-overlap would prevent $M$ from being a matching )  , so if a vertex cover with $|M|$ vertices can be constructed it has to be the minimum vertex cover .

From the definition of bipartite graph we can split the vertex set of the bipartite graph $G$ into two disjoint and independent sets $A$ and $B$  that is every edge connects a vertex in $A$ to one in $B$  . Lets called $P$ the set of unmatched vertices in $A$  and $Q$ be the set of vertices that are either in $P$ or are connected to $P$ by paths that alternate between edges that are in the matching and edges that are not in the matching  \[ \text { Lets say }  Z =  ( A / Q) \cup  ( B \cap Q) \] where $A / Q$ stands for vertices in set $A$ but not in set $Q$ or also known as set minus $A - Q$

Now every edge $e$ in $E$ either belongs to an alternating path (and has a right endpoint in $Z$, or it has a left endpoint in $Z$. If $e$ is matched but not in an alternating path, then its left endpoint cannot be in an alternating path (because two matched edges can not share a vertex) and thus belongs to  $ A / Q $. Alternatively, if $e$ is unmatched but not in an alternating path, then its left endpoint cannot be in an alternating path, for such a path could be extended by adding $e$ to it. Thus, $Z$ forms a vertex cover.

Moreover  every vertex in $Z$ is an endpoint of a matched edge. For, every vertex in $A / Q$ is matched because $Q$ is a superset of $P$ , the set of unmatched left vertices. And every vertex in $B \cap Q $ must also be matched, for if there existed an alternating path to an unmatched vertex then changing the matching by removing the matched edges from this path and adding the unmatched edges in their place would increase the size of the matching. However now  no matched edge can have both of its endpoints in $Z$. Thus $Z$ is a vertex cover of cardinality equal to $|M|$  and must be a minimum vertex cover.
And we are done , phew !!!!

Examples and Problems

Example (Halls Marriage Theorem) : Prove Halls Marriage Theorem using Kőnig-Egerváry theorem 
(If anyone is not aware of Halls marriage theorem can look it up on the web.)

Proof :
In a bipartite graph $G$ let $M$ be the matching of size $|A|$. It is a maximum  cardinality matching because it contains every vertex of A. By König's theorem any minimum  vertex cover $U$ has $|U|=|A|$ vertices. If there was an $S \subseteq A$ such that $|N(S)| < |S|$ then by definition of neighborhood, $N(S)$ would touch the same edges as S but with fewer vertices so $U′ = (U / S) \cup N(S)$ is of strictly smaller cardinality than $U$ and is also a vertex cover of $G$  which is impossible hence we are done. 

Remarks : There are other ways to prove halls marriage theorem, but since we are discussing about konigs theorem I thought of using this to prove halls marriage theorem.

Example (Vietnam TST 2001) : Some club has $42$ members. It’s known that among $31$ arbitrary club members, we can find one pair of a boy and a girl that they know each other. Show that from club members we can choose $12$ pairs of knowing each other boys and girls.

Proof : 
It is clear from the problem that  we must have at least $12$ boys and $12$ girls.
Consider a bipartite graph $G$ with one half of the vertices representing boys and other half vertices as  girls namingly $V_1$ and $V_2$.

Suppose the maximum matching is $k\leq 11$. Then by Konig’s theorem we have minimum possible size of a vertex cover equal to $k$. Let the vertex set in this cover be $V_1$. Then take $G-V_1$. From $k\leq 11$ it follows that $|G-V_1|\geq 31$. So there is an edge between two vertices in $G-V_1$. Hence  $V_1$ is not a vertex cover. 
So its clear that we can choose $12$ pairs satisfying the problems condition .

Example : Prove that a $k-$regular bipartite graph (with $k \ge 1$) has a perfect matching.
Proof : 
Let $G$ be $k-$ regular bipartite graph with the sets $A$ and $B$ ( $V( G) = A \cup B$ where $V(G)$ is the set of all vertices ) . We can see that $|A|=|B|$ as \[ k|A| = \sum_{ \alpha \in A} deg ( \alpha )  = |E| =  \sum_{ \beta \in B} deg ( \beta ) = k|B|  \] We observe that any vertex cover $C$ has at least $|A|$ vertices, since each vertex of $C$ covers exactly $k$ of the $k|A|$ edges. Konig’s Theorem tells us that a maximum matching has at least $|A|$ edges, which is only possible if it has exactly $|A| = |B|$ edges, so it is a perfect matching .

Below are few problems you can try.

USEMO 2021 P1 : Let $n$ be a fixed positive integer and consider an $n\times n$ grid of real numbers. Determine the greatest possible number of cells $c$ in the grid such that the entry in $c$ is both strictly greater than the average of $c$'s column and strictly less than the average of $c$'s row.

Problem : Prove that any bipartite graph $G$ has a matching of size at least $\frac{|E(G)|}{\Delta (G)}$.

Problem : You have an $n$ by $m$ array of $0 's$ and $1 's$. Let $a$ be the most $1 's$ you can pick so that no two are in the same row or column. Pick a sub rectangle (not necessarily non-empty) of zeros which has dimensions $b$ by $c$; that is, pick $b$ special rows and $c$ special columns so that any entry which is in a special row and special column is $0$. Suppose $b+c$ is maximal. Show that $a+b+c=n+m$

Post by Milind Pattnaik.

About the guest blogger: Hi, I am Milind and retired from olympiad yet on my spare time i hop on a few math olympiad problems because they still do excite me . I am interested in electronics , computer science , AI/ML and do competitive programming and math in my spare time.

Post set up and modified by Pranav Choudhary.