MM10  Grafteori  FALL 2006 (instructor Bjarne Toft)

MM10 NEWS NO. 2 (September 13, 2006)

The lecture on Wednesday Sept. 13, 2-4 PM, continues with the interval scheduling problem. Page 3 og the set of notes PRÆMIEOPGAVE contains a description of the problem.

The exercises on Monday Sept. 18, 10-12 AM, will deal with

• Prove König's Theorem that any bipartite graph may be edge-coloured using only the maximum degre number of colours.
• Prove that the Petersen graph cannot be edge using three colours.
• Prove that any bipartite graph of maximum degree 3 has an interval edge colouring (first obtained by henrik Hansen in 1992 in his thesis).
  

• 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.