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
Monday 15:00-17:00 (with break), C 2.09 UZA 4. The lecture will last more than 90
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
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
1.1 What are graphs?
1.2 Eulerian tours *
1.3 What is Graph Theory?
2 Flows, paths and matchings *
2.2 Menger's Theorem for edge separators
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.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
2. Define the terms "capacity", "network", "flow" and "cut" and formulate the
3. Formulate the min-cut-max-flow-Theorem and explain it based on an example of a given
4. Formulate Menger's Theorem for edge-cuts and prove it by using the
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 K5 and
K3,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
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
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
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
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.