# Combinatorics and Graph Theory II

### Lecture on Wednesday 10:40, S11

The tutorials will be led by Andreas
Feldmann on Tuesday at 10:40 in S8.

This page will contain brief summaries of lectures with links to
relevant literature. See the syllabus
in SIS.

#### Topics covered:

- 4. 10.: Characterisation of maximum matchings via augmenting
paths. Blossom contraction and its relationship to maximum matchings.
Edmonds' Blossom algorithm for finding a maximum matching
in a graph [Blo,T]. Note that a part of the correctness proof will be
covered at the tutorial session.
- 11. 10.: Proof of Tutte's characterisation of graphs with a
perfect matching [D]. Proof that every 3-regular 2-connected graph has
a perfect matching (Petersen's theorem) [D].
- 18. 10.: Each 3-connected graph other than K_4 has an edge whose
contraction preserves 3-connectivity; Tutte's characterisation of
3-connected graphs [D]. The notion of graph minor. Kuratowski's and
Wagner's theorem [D].
- 25.10.: Proof of Kuratowski-Wagner completed. Homeomorphism.
Informal introduction to surfaces. Addition of a handle or a cross-cap.
Classification of surfaces, notion of orientable and non-orientable
surface of genus g [D].

- 1. 11.: Generalized Euler's formula, its consequences for average
and minimum degree and degeneracy of graphs embedded on a given
surface, Heawood's upper bound on chromatic number [D].
- 15. 11.: Theorems of Brooks and Vizing [D].
- 22. 11.: Perfect graphs, weak perfect graph theorem [D].
- 29. 11.: Chordal graphs, their characterisation by perfect
elimination scheme, their perfectness [Ba, HR]. Hamiltonicity: the
Bondy-Chvátal theorem on Hamiltonian graphs [BCh].

- 6.
12.: Tutte polynomial of a multigraph, its contraction-deletion
recurrences, its relationship to the chromatic polynomial [Bo].
- 13. 12.: Basics of formal power series. Ordinary generating
functions of combinatorial classes, and the combinatorial meaning of
their sums, products and powers [W].
- 20. 12.: Exponential generating functions, the combinatorial
interpretation of their products and sums [W]. Basic notions of group
actions: fixed points, stabilizers, orbits [Bo].
- 3. 1.: The orbit-stabilizer lemma, the Cauchy-Frobenius formula
(a.k.a. Burnside lemma) in both weighted and unweighted version [Bo].

#### Literature:

[Ba] P. Bartlett: Chordal
graphs (pdf lecture notes)

[BCh] The Bondy
and Chvátal theorem

[Blo] The
Blossom Algorithm

[Bo] B. Bollobás: Modern Graph Theory

[D] R. Diestel: Graph Theory

[EKR] The
Erdős-Ko-Rado theorem

[HR] Y. Haimovitch, A. Raviv: Chordal
graphs (pdf slides)

[T] R. Tarjan: Sketchy
notes on [...] blossom algorithm for general matching

[W] H. Wilf: Generatingfunctionology