Webrelaunch 2020

Graph Theory (Winter Semester 2013/14)

Lecture: Monday 9:45-11:15 1C-03 Begin: 21.10.2013
Wednesday 8:00-9:30 Neue HS Geb. 20.40
Problem class: Friday 11:30-13:00 RPH HS Geb. 40.32 Begin: 25.10.2013
Lecturer Prof. Dr. Maria Axenovich
Office hours: Mon. 13:00-14:00 (available per e-mail or Skype)
Room 1.043 Kollegiengebäude Mathematik (20.30)
Email: maria.aksenovich@kit.edu
Problem classes Torsten Ueckerdt
Office hours:
Room Kollegiengebäude Mathematik (20.30)
Email: torsten.ueckerdt@kit.edu


  • The grades for Graph Theory are published on the 4th floor of Allianz building.
  • The post-exam review takes place on April 28 from 1pm to 2pm in room 1C-01 of Allianz building.
  • Oral reexaminations are possible on individual schedule. Please feel free to contact us.

In summer term 2014 we offer the seminar Topics in Graph Theory. Interested students should come to the kick-off meeting on Thursday, February 6.

For further information see Topics in Graph Theory.

Course description

The course will be concerned with topics in classical and modern graph theory:

  • Properties of trees, cycles, matching, factors
  • Forbidden subgraphs
  • Planar graphs
  • Graph colorings
  • Random graphs
  • Ramsey theory
  • Graph minors


The class is oriented towards problem solving. The goal of the course for
the students is to gain knowledge about the fundamental concepts in graph theory,
solve interesting problems, learn how to write and present the proofs creatively.


basic knowledge of linear algebra; appropriate for students starting from 5th semester


Problem sheets

  • There will be a problem sheet every Monday (starting on October 21) with 4 problems for 5 points each.
  • The problems can be solved in small groups and solutions can be submitted separately or in groups of two or three.
  • Every student works on three problems of his/her choice.
  • Due date is Wednesday the following week at 12:00 am.
  • The problems can be submitted during the lecture or deposited in a box in the 4th floor of Allianz building.

The problem sheets will be handed out in the Monday lecture.

Written exam

There will be a written exam at the end of semester on

February 26, 2014, 9:00am to 1:00pm

The exam takes place in HS Nusselt (building 10.23) und HS Tulla (building 11.40).


Begin: January 15, 2014
End: February 15, 2014

To register for the exam "Graph Theory" go to the student portal at https://studium.kit.edu. The registration is open from 15th of January 15 to 15th of February. Registerations later than February 15 can only be done in person at the secretary. Registrations can be canceled before February 26 via student portal and at February 26 on site in person.

Day of exam

Each student reads up his seat and should be 10 minutes before the exam begins at his/her seat.


The final grade for the course is calculated based on the points achieved in the written exam. If a student passes the written exam then his or her grade can be raised by one, two or three steps. This is done based on the points the student achieved in the homework as follows:

  • At least 108 points on 9 problem sheets or at least 90 points on 7 problem sheets: grade 1 step better
  • At least 115 points on 9 problem sheets or at least 95 points on 7 problem sheets: grade 2 steps better
  • At least 122 points on 9 problem sheets or at least 100 points on 7 problem sheets: grade 3 steps (a full grade) better


The main source is the book Graph Theory by Reinhard Diestel. The English edition can be read for free on the author’s web site (http://diestel-graph-theory.com/).

Additional literature

  • D. West -- Introduction to graph theory
  • B. Bollobas -- Modern graph theory
  • A. Bondy and U.S.R. Murty -- Graph Theory
  • L. Lovasz -- Combinatorial problems and exercises
  • G. Chartrand, L. Lesniak and P. Zhang -- Graphs & Digraphs

Lecture notes

There exist notes taken by a student during the winter term 2011/12. The current version is not approved and claims neither completeness nor correctness.

  • unrevised notes up to Menger's theorem: (pdf)

Additionally, there are lecture notes containing all relevant definitions, notation and theorems from the lecture. However, they provide no proofs, no motivation and only a few examples.

  • lecture notes: (pdf)

Supplementary material

  • Proof example from the problem class on 2013/10/25: (pdf)
  • Program that computes connected components, maximum degree and diameter of word graphs: (tar-ball)

Special thanks go to Daniel Hoske who kindly provides his source code.