401-3052-05L  Graph Theory

SemesterSpring Semester 2018
LecturersB. Sudakov
Periodicityyearly recurring course
Language of instructionEnglish


401-3052-05 VGraph Theory28s hrs
Wed/110:15-12:00HG E 1.1 »
Thu/110:15-12:00HG E 1.1 »
B. Sudakov
401-3052-05 UGraph Theory7s hrs
Thu/115:15-16:00CAB G 52 »
15:15-16:00CAB G 56 »
15:15-16:00HG D 5.3 »
15:15-16:00HG E 21 »
15:15-16:00ML J 34.1 »
B. Sudakov

Catalogue data

AbstractBasic notions, trees, spanning trees, Caley's formula, vertex and edge connectivity, blocks, 2-connectivity, Mader's theorem, Menger's theorem, Eulerian graphs, Hamilton cycles, Dirac's theorem, matchings, theorems of Hall, König and Tutte, planar graphs, Euler's formula, basic non-planar graphs, graph colorings, greedy colorings, Brooks' theorem, 5-colorings of planar graphs
ObjectiveThe students will get an overview over the most fundamental questions concerning graph theory. We expect them to understand the proof techniques and to use them autonomously on related problems.
Lecture notesLecture will be only at the blackboard.
LiteratureWest, D.: "Introduction to Graph Theory"
Diestel, R.: "Graph Theory"

Further literature links will be provided in the lecture.
Prerequisites / NoticeNOTICE: This course unit was previously offered as 252-1408-00L Graphs and Algorithms.

Performance assessment

Performance assessment information (valid until the course unit is held again)
Performance assessment as a semester course
ECTS credits5 credits
ExaminersB. Sudakov
Typesession examination
Language of examinationEnglish
RepetitionThe performance assessment is only offered in the session after the course unit. Repetition only possible after re-enrolling.
Mode of examinationwritten 180 minutes
Additional information on mode of examinationThe exams for the two course units 401-3052-10L (core course 4V+1U) and 401-3052-05L (elective course 2V+0.5U) take place simultaneously (3 hours).
Written aidsYou may use a printed (unmarked) copy of the lecture notes and 5 A4 pages of personal notes written front and back. (In particular you may thus not bring books.)
This information can be updated until the beginning of the semester; information on the examination timetable is binding.

Learning materials

Main linkMoodle webpage of the course
Only public learning materials are listed.


No information on groups available.


There are no additional restrictions for the registration.

Offered in

CAS in Computer ScienceFocus Courses and ElectivesWInformation
Computational Biology and Bioinformatics MasterAdvanced CoursesWInformation
Computational Biology and Bioinformatics MasterTheoryWInformation
Data Science MasterCore ElectivesWInformation
Computer Science MasterFocus Elective Courses Theoretical Computer ScienceWInformation
Computer Science MasterElective Focus Courses General StudiesWInformation