The lecture on Wednesday Sept. 20,
2-4 PM, deals with the matching problem. We
first define the concepts matching, maximal matching,
maximum matching and perfect matching (1-factor). We
shall then consider
The Berge (1957)-Petersen(1891) Theorem (A matching M in a graph G is maximum if and only if there is no augmenting path wrt M in G). The proof is relatively easy. The theorem is described in Section II.2 of Algoritmisk Kombinatorik and in the notes PRÆMIEOPGAVE p. 14. This theorem is NOT a good theorem!
The Theorem of König 1931 (In a bipartite graph the size of a maximum matching equals the size of a minimum covering of the edges by vertices). The proof is by an algorithm. This is described in Section II.2 in Algoritmisk Kombinatorik. König's theorem is a GOOD theorem.
The Theorem of Tutte 1947 (A graph G has a perfect matching if and only if for all subsets X of V(G) the graph G-X has at most |X| odd connected components). Tutte proved this by an algebraic technique. We give a short proof from the paper [ L. Lovász, Three short proofs in graph theory, Journal Comb. Theory B 19 (1975), p. 269-271]. Tutte's Theorem is a GOOD theorem.
The algorithm of Edmonds 1965 (Input: Graph G. Output: either a perfect matching M in G or a subset X of V(G) such that G-X has > |X| connected components). This algorithm is described in the notes PRÆMIEOPGAVE on p. 22. This gives an alternative proof of Tutte's Theorem based on a GOOD (i.e. Polynomial) algorithm.
The classes on Monday Sept. 25 10-12 AM and Wednesday Sept. 20 2-4 PM will be given by Professor Michael Stiebitz, Technical University of Ilmenau, Germany. The lecture on Monday will deal with Menger's Theorem. The lecture on Wednesday will deal with Flows in Networks. A set of notes will be distributed.
The exercises on Monday Oct. 2, 10-12 AM, will (perhaps! ) deal with
The sequence of problems 1, 2, 3, ...Problem 7 asks for a proof of Petersen's Even factor Theorem (that any 2r-regular graph can be factorized into r 2-factors).
Problem 1: The sum of the degrees in any graph is an even number.
Any graph has an even number of vertices of odd degree.
Problem 2:
A graph where alle vertices have even degree cannot have a bridge (a
bridge is an edge xy whose removal leaves x and y in different
components of the remaining graph).
Problem 3. Let G be a graph
with at least one edge and all degrees even. Prove that G has a
closed Eulerian trail (a sequence of different consequtive edges,
covering each edge of G exactly once, and ending in the vertex where
it started). This is EULER's THREOREM.
Problem 4: Any 4-regular
graph may be divided into two 2-factors.
Problem 5: In a graph of
maximum degree 4 the edge set may be divided into two classes, such
that any vertex of the graph is incident with at most two edges from
each class.
Problem 6: In a graph of maximum degree 2r the edgeset
may be divided into r classes, such that any vertex of the graph is
incident with at most two edges from each class.
Problem 7: Any
2r-regular graph may be divided into r 2-factors.
Loose ends from the matching lecture – in particualar prove Hall's Theorem (1936): A bipartite graph has a matching satisfying all vertices in the left side if and only if for any subset X of the vertices in the left side the number of neighbours of X in the right hand side is at lest |X|.
Loose ends and problems from the set of notes on Connectivity in graphs and flows in networks: Menger's Theorem and Ford-Fulkerson's Algorithm.
The reason for the perhaps! is that on Monday Oct.2 we have at least 3 guests in the department: Professor Michael Stiebitz, Germany, professor Robin Wilson, England, and professor Jack Edmonds, Canada. Perhaps one of them will come along to the class.