Project Min-Max Theorems in Graph Theory
(suggested content)
(due 10pm Dec 8)
In graph theory, there are many theorems of min-max type. These theorems
Project Min-Max Theorems in Graph Theory
(suggested content)
(due 10pm Dec 8)
In graph theory, there are many theorems of min-max type. These theorems have a common
form of statements which assert that the maximum size of an X-set is equal to the minimum
size of a Y -set in a (certain) graph where X and Y are properties of a set. The König-Egerváry
Theorem is such a theorem.
This project is intended for a short survey of min-max theorems which you have learned from
the course or come across from the literature. It must contain at least six min-max theorems
(including König-Egerváry Theorem) and in addition the following:
• definitions (with illustration examples) for the terms used in each theorem;
• precise statement of each theorem (no proof is needed);
• (in case the theorem does not hold for all graphs) examples that show the theorem fails;
• optimization problems related to the theorem;
• comments on the algorithmic importance of the theorem;
• References.
1
