620-352 Graph Theory

Twenty-five points from the following: 200-level science mathematics subjects, 200-level science statistics subjects, computer science 433-253.

This subject introduces the basic concepts of graph theory including paths and cycles, trees and counting, automorphism groups, planar graphs, colouring properties, chromatic polynomials, matching theory. Students should develop the ability to implement algorithms on graphs for finding objects such as minimum spanning trees, maximum matchings and flows; and to implement approximation algorithms. This subject demonstrates the variety of applications of graph theory both within and outside mathematics.

Introduction to graph theory topics include basic concepts, paths and cycles, trees and counting, combinatorics, matching theory, and probabilistic method. Algorithms topics include minimum spanning trees, maximum matchings, flows, approximation algorithm.

Up to 24 pages of written assignments and a 3-hour end-of-semester written examination.