Introduction to Graph Theory

Education facts

Code: 5MA146

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.

Entry requirements

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

Education offerings

Each offering has its own dates and conditions. Closed offerings are retained as history and do not mean that a new application is open.

• Introduction to Graph Theory

  Umeå University

  Start date: 25 March 2027

  End date: 6 June 2027

  Pace of study: 50 %