VVZ API is not affiliated with ETH Zurich. Data might be outdated or incorrect. Please view the official ETHZ Vorlesungsverzeichnis for binding information.

401-3052-05L 5 Credits BSC , MSC D-BSSE , D-INFK , D-MATH , D-PHYS , D-ITET

Introduction to Graph Theory

Lecturers & Examiners: Prof. Dr. Benjamin Sudakov

This is the first half of the course unit 401-3052-10L Graph Theory. Notice that at most one of the two course units 401-3052-05L Introduction to Graph Theory and 401-3052-10L Graph Theory can be recognised for credits.

VVZ CR n/a

Last Updated: 2026-06-03 00:14:12

Abstract

Basic notions, trees, spanning trees, Caley's formula, vertex and edge connectivity, 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

Objective

The 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.

Resources

Lecture Notes

Lecture will be only at the blackboard.

Literature

West, D.: "Introduction to Graph Theory" Diestel, R.: "Graph Theory" Further literature links will be provided in the lecture.

Learning Materials (Links)

Moodle course
Moodle-Kurs / Moodle course

General Information

Language: English
Levels: BSC , MSC
Frequency: Yearly recurring

Examination

Type: session examination
Mode: written 180 minutes
Aids: Students are allowed to bring ONLY a printed copy of the lecture notes with no extra writing (highlighting and blank post-its are allowed).

The 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).

Course Components

Type	Title	Time & Place	Hours
lecture	Introduction to Graph Theory	Wed 10:15-12:00 (HG E 5) Thu 10:15-12:00 (HG F 3)	28 h semesterly
exercise	Introduction to Graph Theory	Fri 12:15-13:00 (HG E 1.1) Fri 12:15-13:00 (ML F 39) Fri 16:15-17:00 (HG D 5.2) Fri 16:15-17:00 (HG E 1.1)	7 h semesterly

Offered In

Mathematics Bachelor
- Electives
  - Selection: Mathematical Optimization, Discrete Mathematics
- Bachelor Studies (Programme Regulations 2024 resp. 2021)
  - Compulsory Elective Courses (Programme Regulations 2024 and 2021)
Physics Bachelor
- Electives
Computational Biology and Bioinformatics Master (More informations at: )
- Advanced Courses (A total of 30 ECTS needs to be acquired in the Advanced Courses category. Thereof at least 16 ECTS in the Theory and 10 ECTS in the Biology category.)
  - Theory (At least 16 ECTS need to be acquired in this category.)
Electrical Engineering and Information Technology Master
- 01 - Courses of specializations
  - Track: Signal Processing and Machine Learning (The core courses and specialization courses below are a selection for students who wish to specialize in the area of "Signal Processing and Machine Learning ", see . The individual study plan is subject to the tutor's approval.)
    - Specialization Courses (These specialization courses are particularly recommended for the area of "Signal Processing and Machine Learning", but you are free to choose courses from any other field in agreement with your tutor. Semester / Research Projects are not allowed in this category. A minimum of 40 credits must be obtained from specialization courses during the MSc EEIT.)