Graph theory

Summary

The course aims to introduce the basic concepts and results of modern Graph Theory.

Content

Show more

Keywords

Graph, isomorphism, complement, complete, bipartite, connected, path, circuit, cycle, planar, tree, spanning, Eulerian, Hamiltonian, colouring, Ramsey theory, forbidden subgraph, extremal graph.

Learning Outcomes

By the end of the course, the student must be able to:

• Illustrate simple examples of graphs satisfying certain properties
• State definitions and results of graph theory
• Verify hypotheses of theorems for applications
• Prove theorems and other properties
• Justify the main arguments rigorously
• Apply relevant results to solve problems
• Modify the main proofs if needed, to solve similar problems

Teaching methods

In-person lectures + in-person exercise classes covering weekly exercise sheets.

Expected student activities

The students are expected to attend the lectures and the exercise classes. In addition, they are expected to attempt the problems on the exercise sheets and to submit their solutions of a selected subset of the exercises for grading.

Assessment methods

Written final exam

Supervision

Office hours	No
Assistants	Yes
Forum	Yes

Resources

Bibliography

• Diestel : Graph Theory (Springer)
• Bollobas : Modern Graph Theory (Springer)
• West: Introduction to Graph Theory

Ressources en bibliothèque

• Find the references at the Library

Notes/Handbook

Lecture notes will be provided.

Moodle Link

• https://go.epfl.ch/MATH-360

Prerequisite for

MATH-467: Probabilistic methods in combinatorics

MATH-526: Algebraic methods in combinatorics