Graph Theory and Algorithms

6 EC

Semester 2, period 4, 5

5122GRTO6Y

Owner Bachelor Wiskunde
Coordinator dr. K. Guo
Part of Exchange Programme Faculty of Science, specialisation BSc Mathematics, year 1Minor Mathematical Themes, year 1Bachelor Mathematics, year 2Double bachelor Mathematics and Physics, year 2Double bachelor Mathematics and Computer Science, year 2
Links Visible Learning Trajectories

Course manual 2025/2026

Course content

This following topics will be covered in the course:

  • Trees - properties of trees, exchange property, Kruskal's algorithm, Dijkstra's algorithm
  • Matchings - augmenting paths, Hall’s Theorem, König-Egerváry Theorem, duality between independent sets and edge covers, Hungarian algorithm 
  • Connectivity - blocks, ear decompositions, Menger's Theorem
  • Graph Colouring - basic bounds for chromatic number, Brooks' Theorem, existence of graphs with high girth and chromatic number, chromatic polynomial 
  • Planar graphs - Recap of results from previous course, characterising planar graphs (Kuratowski’s Theorem)(depending on time)
  • Extremal graph theory / Ramsey theory [Turan's theorem, Erdos-Stone theorem, Ramsey Theorem (depending on time)

Study materials

Literature

  • Doug West "Introduction to Graph Theory"

Syllabus

  • It is recommended that you take notes during lectures.

     

    Further examples, explanations, exercises can be found in Doug West's book.

Other

  • Extra material can be found on canvas

Objectives

  • The student should be able to reproduce definitions and statements of theorems from the course;
  • The student should be able to reproduce proofs from the course by summarising and remembering the main ideas/steps;
  • The student should be able to check if definitions have been satisfied, to give examples and non-examples of objects satisfying the definition, and to derive simple consequences from definitions;
  • The student should be able to apply results from the course to solve unfamiliar problems in graph theory;
  • The student should be able to generalise proofs in simple ways and be able to analyse where in a proof certain assumptions have been used;
  • The student should be able to apply mathematical/combinatorial proof techniques such as proofs by induction, proofs by contradiction, use of the extremal principle, to problems in graph theory;
  • The student should be able to apply algorithms from the course to given instances of relevant optimisation problems;
  • The student should be able to write clear mathematics proofs and explain their ideas in a clear way.

Teaching methods

  • Lecture
  • Self-study

Learning activities

Activiteit

Aantal uur

Lectures

30

Exercise classes

28

Mid-term exam

3

Final exam

3

Self-study

104

Attendance

Attendance requirements for the program (OER - Part B):

  • Active participation is expected from every student in the course component for which the student is enrolled.
  • In addition to the general requirement that the student actively participates in the education, the additional requirements per component are described in the study guide. It also specifies which parts of the component have a mandatory attendance requirement.
  • If a student is unable to attend a mandatory part of the program due to personal circumstances, the student must report this in writing as soon as possible to the relevant lecturer and the study advisor.
  • It is not permitted to miss mandatory parts of a component if there are no personal circumstances.
  • In cases of qualitatively or quantitatively insufficient participation, the examiner may exclude the student from further participation in the component or part of it. Conditions for sufficient participation are determined in advance in the study guide and on Canvas.

Assessment

Item and weight Details

Final grade

0.7 (70%)

Tentamen

0.3 (30%)

Deeltoets

Continuous assessment (i.e. homework) counts 25% towards your final grade. There will be 6 exercise sheets and your best 5 marks will count towards the 25%. Combinatorial problem solving is an important part of this course and is assessed mainly through the homework. The remaining 75% is assessed via the final exam. There is no midterm exam. You must score at least  50% on the exam  to pass the course.

You may only take the resit exam if you score at least half marks on the continuous assessment.  If you take the resit exam, the continuous assessment only counts 25% towards your mark if it increases your grade; otherwise the resit exam counts 100% towards your final grade.

 

Inspection of assessed work

Contact the course coordinator to make an appointment for inspection.

Assignments

There will be 6 homework assignments each consisting of around 6 problems. These will be graded and your best 5 out of 6 marks will count  25% towards your final grade. You will hand in solutions to 3 or 4 of the problems on each exercise sheet; some of these will be marked and returned to you. You may work in groups to solve the problems, but each student must write their own solutions for submission. You will find the homework assignments on canvas.

 

Fraud and plagiarism

The 'Regulations governing fraud and plagiarism for UvA students' applies to this course. This will be monitored carefully. Upon suspicion of fraud or plagiarism the Examinations Board of the programme will be informed. For the 'Regulations governing fraud and plagiarism for UvA students' see: www.student.uva.nl

Course structure

Weeknummer Onderwerpen Studiestof
1 Recap on the basic notation and terminology. Begin the section on trees proving three equivalent characterisations of trees.   
2 Other characterisation of trees. Exchange property for trees. Description of Kruskal's algorithm. Proof of correctness of Kruskal's algorithm.  
3 Description of Dijkstra's algorithm. Proof of correctness of Dijkstra's algorithm.  
4 Begin topic on matchings. Several definitions. Characterise maximum matchings in terms of augmenting paths. Statement and proof of Hall's Theorem.  
5 State and prove various results relating the sizes of maximum independent sets / matchings and minimum vertex / edge covers in (bipartite) graphs. In particular, prove the Konig-Egervary Theorem, Gallai's Theorem, and Konig's Theorem.  
6 Description and proof of correctness of maximum matching algorithm in bipartite graphs. Description of the Hungarian algorithm for finding maximum weight perfect matchings in weighted bipartite graphs.   
7 Proof of correctness for the Hungarian Algorithm. Relationship between the various algorithmic problems  studied and the famous P vs NP problem. Begin section of graph connectivity, defining the various notions of connectivity and how they relate to each other.  
8 Define the notion of blocks and prove various properties of blocks. Understand the structure of connected graphs in terms of blocks by showing that the block-cutpoint graph is a tree.  
9 Understand the structure of 2-connected graphs. State and prove Menger's Theorem for the case of 2-connected graphs and characterise 2-connected graphs in terms of ear decompositions. Begin proof of Menger's Theorem in full generality.  
10 Finish poof of Menger's Theorem. Recall various definitions and results related to graph colouring including the greedy colouring algorithm. Describe intelligent greedy colouring, i.e. the Szekeres-Wilf Theorem. State Brooks' Theorem.  
11 Prove Brooks' Theorem. Describe Mycielski's construction for triangle-free graphs with large chromatic number.  
12 Use the probabilistic method to show the existence of graphs with large girth and chromatic number. Define the chromatic polynomial and show it is a polynomial. State and prove the deletion-contraction recursion for the chromatic polynomial.   
13 Recap on planar graphs. State Kuratowski's Theorem. Proved the easy direction and half of the hard direction.  
14 Finish the proof of Kuratowski's Theorem.  
15 Revision  
16 Revision  

Honours information

There is no honours extension for this course.

Additional information

Recommended prior knowledge: Basiswiskunde, Inleiding Grafentheorie.

The course will be given in English.

Contact information

Coordinator

  • dr. K. Guo

Staff

  • Mehmet Akif Yildiz (m.a.yildiz@uva.nl