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

Constructions in Number Theory

Hi, I am Emon, a ninth grader, an olympiad aspirant, hailing from Kolkata. I love to do olympiad maths and do some competitive programming in my leisure hours, though I take it seriously. I had written INOI this year. Today, I would be giving you a few ideas on how to Construct in Number Theory . Well, so we shall start from the basics and shall try to dig deeper into it with the help of some important and well-known theorems and perhaps, some fancy ones as well. Okay, so without further delay, let's start off... What do we mean by "Constructions"? If noticed, you can see that you often face with some problems in olympiad saying, "... Prove that there exists infinitely many numbers satisfying the given conditions" or "... Prove that there exists a number satisfying the above conditions." These are usually the construction-problems .  For example, let's consider a trivial example : Problem. Prove that there exist infinitely many integers $a$ such th

EGMO solutions, motivations and reviews ft. Atul, Pranjal and Abhay

The  European Girls' Mathematical Olympiad a.k.a EGMO 2022 just ended. Congrats to Jessica Wan from USA, Taisiia Korotchenko, and Galiia Sharafetdinova for the perfect scores! Moreover, the Indian girls brought home 4 bronze medals! By far, this is the best result the EGMO India Team has ever achieved! To celebrate the brilliant result, here's a compilation of EGMO 2022 solutions and motivations written by my and everyone's favorite IMOTCer Atul ! And along with that, we also have reviews of each problem written by everyone's favorite senior, Pranjal !  These solutions were actually found by Atul, Pranjal,  and Abhay  during the 3-hour live solve. In the live solve, they solved all the 6 problems in 3 hours 😍!!! Okie Dokie, I think we should get started with the problems! Enjoy! Problem 1:  Let $ABC$ be an acute-angled triangle in which $BC<AB$ and $BC<CA$. Let point $P$ lie on segment $AB$ and point $Q$ lie on segment $AC$ such that $P \neq B$, $Q \neq C$ and

Q&A with experts about bashing

Heyy everyone! From the title, you can see that we are going to talk about  BASH.  Yesss, we are going to discuss whether you really need to learn bash or not?  Let me first introduce myself, I am Pranav Choudhary, a 10th grader from Haryana(India). I like to do geo and combo the most :PP. Oki so let's begin! For those of you who don't know what bashing is, lemme give you a brief introduction first. Bashing is basically a technique used to solve Geometry Problems. In general, when you try a geo problem you might think of angles, similarities, and some other techniques (e.g. Inversion, spiral similarity etc). All of which are called synthetic geometry. But sometimes people use various other techniques called "bash" to solve the same problems.  Now there are different kinds of bashing techniques, e.g. - Coordinate bash, Trig Bash, Complex bash, Barycentric Coordinates. Let me give you a brief introduction to each of them.  Coordinate Bash : You set one point as the orig