New: There will be an exam on "Graph Theory" on November 15 at 10am. Students who want to participate should contact me by November 11.

LV-Nr. 250047 lecture "Graph Theory", 2 hours a week (3 ECTS). The lecture will be given in English if there are one or more students who do not speak German fluently. The examination will be written and oral.

Monday 15:00-17:00 (with break), C 2.09 UZA 4. The lecture will last more than 90 minutes, because it will be cancelled one or two times.

In the first part of the lecture we will discuss some classical theorems from finite structural graph theory. For this I recommend the book
R. Diestel, Graph Theory, Springer.
A new 4th edition is now available. The book contains more than we will need for the lecture.

In the second part we will consider group-theoretical aspects of graph theory like Cayley-graphs, automorphisms and ends of graphs.

The following contents will be updated regularly. A * indicates that most of the section can be found in the lecture notes on "Diskrete Mathematik" of Prof. Fulmek held in winter term 2009.


1 Introduction
1.1 What are graphs?
1.2 Eulerian tours *
1.3 What is Graph Theory?

2 Flows, paths and matchings *
2.1 Max-flow-min-cut-Theorem
2.2 Menger's Theorem for edge separators
2.3 Matchings
2.4 Connectivity and Menger's Theorem for vertex separators

3 Plane graphs
3.1 Isomorphisms an embeddings
3.2 Euler's Formula * and applications
3.3 Platonic graphs
3.4 Coloring plane graphs *
3.5 Kuratowski's Theorem and Minor Theory

4 Cayley Graphs
4.1 Cayley Graphs and the Theorem of Sabidussi
4.2 Free gropups and presentations
4.3 Examples of presentations and Cayley graphs

5 Ends of graphs
5.1 The End Topology
5.2 Compactness
5.3 The 1-2-Cantor Theorem

The examination will be written and oral. In the written part you will get some questions from the list below. The list is preliminary and not complete yet. One or the other question might be changed before the next exam.

1. Formulate and prove Euler's Theorem on closed Eulerian walks in finite graphs with only even vertex degrees.
2. Define the terms "capacity", "network", "flow" and "cut" and formulate the min-cut-max-flow-Theorem.
3. Formulate the min-cut-max-flow-Theorem and explain it based on an example of a given network.
4. Formulate Menger's Theorem for edge-cuts and prove it by using the min-cut-max-flow-Theorem.
5. Formulate König's Theorem and prove it by using the min-cut-max-flow-Theorem or Menger's Theorem for edge-cuts.
6. Formulate König's Theorem and the Marriage Theorem. Prove the Marriage Theorem by using König's Theorem.
7. Explain the difference between the terms "plane graph" and "planar graph". For a given graph, use Kuratowski's Theorem to decide whether the graph is planar or not.
8. Formulate and prove the Eulerian formula for finite plane graphs.
9. Formulate and prove a formula which uses the girth of planar graphs and which can be used to show that the graphs K₅ and K_3,3 are not planar. You will get an example of a graph for which you should use this criterion in order to show that it is not planar.
10. Show that every finite planar graph has a vertex of degree less or equal 5. You are only allowed to use Euler's formula, but no other identities.
11. Define Platonic solids (as graphs) and give a sketch of the proof that there are only 5 of them.
12. Formulate and prove the 5-color-Theorem.
13. Formulate Kuratowski's Theorem. What is the connection between minors and subdevided subgraphs in the context of Kuratowski's Theorem. You will get an example of a graph in this context (we have discussed the Peterssen graph).
14. What is the connection bteween minors and subdevided subgraphs in general? You will get an example of graphs in this context.
15. Formulate the Minor-Theorem (Structure Theorem) of Robertson and Seymour and define the corresponding terms.
16. Determine the forbidden minors for examples of minor closed sets of isomorphy classes. Discuss the examples which have been discussed in the lecture.
17. Determine finite and infinite Cayley-graphs for given presentations.
18. Determine a presentation and a connected Cayley-graph of the automorphism group of some given graph.
19. Formulate the Theorem of Sabidussi. Define color-regularity and the closed path property.
20. Define ends and the end toplogy.
21. Determine open and closed sets in the end topology and limits of sequences, in general and in particular for examples of Cayley graphs.
22. Sketch the proof of the fact that in locally finite connected graphs, any infinite descending sequence of radial components with the same centre contains a geodesic ray and that there is precisely one end which lives in all these components.
23. Sketch the proof of the fact that the end topology of a locally finite graph is sequentially compact. You may use that fact in locally finite connected graphs, any infinite descending sequence of radial components with the same centre contains a geodesic ray and that there is precisely one end which lives in all these components.
24. Define the terms transitive action, almost transitive action, abelsian action and formulate the 1-2-Cantor Theorem for abelsian group actions. Discuss examples in this context.
25. Show that the commutator subgroup of a free group of rank two acts abelsian on its freely generated Cayley-graphs, but it does not act almost transitively.