VVZ API is not affiliated with ETH Zurich. Data might be outdated or incorrect. Please view the official ETHZ Vorlesungsverzeichnis for binding information.
Graph Theory
Graph Theory (in English)
Last Updated: 2026-02-05 15:07:02
Abstract
Introduction to the theory of graphs with a great emphasis given to reading, understanding and developing proofs. Topics include: trees, cycles, Eulerian circuits, bipartite graphs, extremality (Erdos-Stone Thm), matchings (Hall's and Tutte's Thm), connectivity (Menger's Thm), colorings (Brooks', Dirac's, Vizing's Thm), list-colorings (Galvin's Thm), planarity (Euler's Formula, Five Color Thm).
Content
This course is an introduction to the theory of graphs. It is intended for students in mathematics and computer science / engineering students with an interest in theory. We start from basic definitions and examples, but hope to move on quickly and cover a broad range of topics. Some applications and relations to Computer Science will also be discussed. Emphasis will be given to reading, understanding and developing proofs. There is no prerequisite, other than basic mathematics introduced in the Grundstudium. Possible topics include: degrees, paths, trees, cycles, Eulerian circuits, bipartite graphs, extremality, matchings, connectivity, network flows, vertex and edge colorings, Hamiltonian cycles and planarity.
Resources
Literature
Douglas B.West, Introduction to Graph Theory - Second edition, Prentice Hall 2001.
General Information
- Language
- English
- Levels
- BSC , DS , MSC
- Frequency
- Yearly recurring
Examination
- Type
- session examination
- Mode
- written 120 minutes
- Aids
- Ein Blatt A4 einseitig (durch Student vorbereitet).
Course Components
| Type | Title | Time & Place | Hours |
|---|---|---|---|
| lecture | Graph Theory (in English) |
|
2 h weekly |
| exercise | Graph Theory (in English) |
|
1 h weekly |