Skip to main content

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.

Comments

Popular posts from this blog

The importance of "intuition" in geometry

Hii everyone! Today I will be discussing a few geometry problems in which once you "guess" or "claim" the important things, then the problem can easily be finished using not-so-fancy techniques (e.g. angle chasing, power-of-point etc. Sometimes you would want to use inversion or projective geometry but once you have figured out that some particular synthetic property should hold, the finish shouldn't be that non trivial) This post stresses more about intuition rather than being rigorous. When I did these problems myself, I used freehand diagrams (not geogebra or ruler/compass) because I feel that gives a lot more freedom to you. By freedom, I mean, the power to guess. To elaborate on this - Suppose you drew a perfect  diagram on paper using ruler and compass, then you would be too rigid on what is true in the diagram which you drew. But sometimes that might just be a coincidence. e.g. Let's say a question says $D$ is a random point on segment $BC$, so maybe

LMAO Revenge

Continuing the tradition of past years, our seniors at the Indian IMO camp(an unofficial one happened this year) once again conducted LMAO, essentially ELMO but Indian. Sadly, only those who were in the unofficial IMOTC conducted by Pranav, Atul, Sunaina, Gunjan and others could participate in that. We all were super excited for the problems but I ended up not really trying the problems because of school things and stuff yet I solved problem 1 or so did I think. Problem 1:  There is a   grid of real numbers. In a move, you can pick any real number  ,  and any row or column and replace every entry   in it with  .  Is it possible to reach any grid from any other by a finite sequence of such moves? It turned out that I fakesolved and oh my god I was so disgusted, no way this proof could be false and then when I was asked Atul, it turns out that even my answer was wrong and he didn't even read the proof, this made me even more angry and guess what? I was not alone, Krutarth too fakesol

Edge querying in graph theory

In this post, I will present three graph theory problems in increasing difficulty, each with a common theme that one would determine a property of an edge in a complete graph through repeated iterations, and seek to achieve a greater objective. ESPR Summer Program Application: Alice and Bob play the following game on a $K_n$ ($n\ge 3$): initially all edges are uncolored, and each turn, Alice chooses an uncolored edge then Bob chooses to color it red or blue. The game ends when any vertex is adjacent to $n-1$ red edges, or when every edge is colored; Bob wins if and only if both condition holds at that time. Devise a winning strategy for Bob. This is more of a warm-up to the post, since it has a different flavor from the other two problems, and isn't as demanding in terms of experience with combinatorics. However, do note that when this problem was first presented, applicants did not know the winner ahead of time; it would be difficult to believe that Bob can hold such a strong