Graph theory
Summary
The course aims to introduce the basic concepts and results of modern Graph Theory.
Content
In this course we will cover the following topics:
- trees
- connectivity
- Eulerian and Hamiltonian cycles
- matchings
- planar graphs
- graph colouring
- Ramsey theory
- extremal problems
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
Notes/Handbook
Lecture notes will be provided.
Moodle Link
Prerequisite for
MATH-467: Probabilistic methods in combinatorics
MATH-526: Algebraic methods in combinatorics
Dans les plans d'études
- Semestre: Automne
- Forme de l'examen: Ecrit (session d'hiver)
- Matière examinée: Graph theory
- Cours: 2 Heure(s) hebdo x 14 semaines
- Exercices: 2 Heure(s) hebdo x 14 semaines
- Type: optionnel
- Semestre: Automne
- Forme de l'examen: Ecrit (session d'hiver)
- Matière examinée: Graph theory
- Cours: 2 Heure(s) hebdo x 14 semaines
- Exercices: 2 Heure(s) hebdo x 14 semaines
- Type: optionnel
- Semestre: Automne
- Forme de l'examen: Ecrit (session d'hiver)
- Matière examinée: Graph theory
- Cours: 2 Heure(s) hebdo x 14 semaines
- Exercices: 2 Heure(s) hebdo x 14 semaines
- Type: optionnel