Petersen grafen hugget ud i sandsten!
Se: www.princeton.edu/
The lecture on Wednesday Oct. 11,
2-4 PM, gives two different proofs of Tutte's Theorem. One is from the
paper "Three short proofs in graph theory" by Lovász (handed out
earlier), and the second is from the notes "PRĈMIEOPGAVE" Opgave 18,
page 22 (handed out earlier).
Tutte's
Theorem (1. formulation) :
A graph G has a 1-factor if and only if G-X has at most |X| odd
components for all subsets X of V(G).
Tutte's
Theorem (2. formulation) :
Let G be any graph. Then
either G has a 1-factor
or V(G) has a subset X
such that G-X has > |X| odd components
Not both!
In the second formulation the either-or statement provides an EP-formulation of Tutte's Theorem (EP stands for Existentially Polytime, meaning that the Theorem claims the existence of something which is easy to recognize when you have it. Very often an EP theorem can be proved by a polynomial-time algorithm which finds an instance of what it says exists. The second proof above is such an algorithmic proof (due to Jack Edmonds). With the "Not both" added, the EP-formulation becomes what is called a good theorem since the existence of X is a certificate for the non-existence of a 1-factor (and vice versa).
The week 42 (Oct. 16-22, 2006) is the autumn holyday week.
The exercises on Monday Oct. 23, 10-12 AM, are cancelled due to BROBYGNING for high
school students. For the same reason the lecture on Wednesday Oct. 25
is only one hour (15:15-16:00).