Introduction to Graph Theory 7.5 credits

About the course

The course treats grapph theoretical notions and problems, and the use of algorithms, both in the mathematical theory of graphs and its applications. In the course, the basic theory of graphs of different kinds is developed in detail, especially trees and bipartite graphs. In the course some of the algorithms that totally or partly solve graph theoretical problems are presented. An example of such a problem is to find a matching of maximum weight, and another is to find a maximum flow in a network. The theory for matchings and Hall's theorem are treated, as well as spanning trees and Menger's theorem. Further, the theory of vertex and edge colouring, including Brooks' theorem and Vizing's theorem, are presented. Finally, an introduction to matroid theory is included.

Show syllabus

Apply

Explore your future at Umeå University

Join a vibrant academic community where high-quality education meets groundbreaking research in science, technology, humanities, and the arts. At Umeå University, you will learn from passionate, expert teachers and benefit from a close connection between research, education, collaboration, and innovation.

World's most satisfied international students

#1 globally in the main categories of Living, Support, and Overall Satisfaction.
A university with health at its core

Umeå University is certified as a Healthy Campus, with many initiatives that promote health and well-being.