The course treats graph theoretical concepts and problems, both theoretically and in applications. In the course, the basic theory of different types of graphs is given in detail, especially for trees and bipartite graphs. In the course is also presented some of the algorithms that partially or completely solve certain graph theoretical problems. Examples of such problems are finding a maximum weight matching, and finding a maximal flow in a network. The theory of matchings and Hall's theorem are treated, together with spanning trees and Menger's theorem. Furthermore, the theory of vertex and edge colorings is treated, including Brooks' theorem and Vizing's theorem. The course concludes with an introduction to matroid theory.
The course requires courses in Mathematics, minimum 60 ECTS or at least two years of university studies and in both cases a course in discrete mathematics, minimum 7,5 ECTS or equivalent. Proficiency in English equivalent to the level required for basic eligibility for higher studies. Where the language of instruction is Swedish, applicants must prove proficiency in Swedish to the level required for basic eligibility for higher studies