902416 VO Selected Topics in Graph Theory (2005S)

I decided to choose matching theory as the topic of this course since it is an example of a well-developed theory in the relatively young branch of mathematics called graph theory.
The intereset in matchtings arose from the following observation of Tait (1880): "The
four-colour theorem is equivalent to the statement that every planar cubic graph without
cut edges is 3-edge-colourable." Using this observation, Tait wanted to prove the four-colour theorem. Although he failed with this project, his efforts led to a beautiful theory.

I will start the course with the fundaments of matching theory, i.e. Hall's Theorem, Tutte's Theorem and Edmonds' Algorithm for finding a matching of maximal size.
Then we will turn to the perfect matching polytope, which is defined as the set of convex
combinations of perfect matchings in a vector space naturally associated to every graph. Finally we will consider the matching lattice, being the set of integer linear combinations of perfect matchings.