Introduction to Graph Theory, 7.5 Credits

Contents

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.

Expected learning outcomes

For a passing grade, the student must be able to

Knowledge and understanding

• define basic notions in graph theory and matroid theory
• account for the basics in chromatic graph theory
• account for basic properties of matchings
• account for the theory of paths and the degree of connectedness of a graph
• account for basic matroid theory
• prove the theorems that are treated in the course

Skills and abilities

• apply the algorithms that are treated in the course for solving graph theoretical problems
• apply the theorems that are treated in the course for problem solving and proofs

Judgment and approach

• decide in what situations the theorems that are treated in the course can be applied

Required Knowledge

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

Form of instruction

Teaching is mainly in the form of lectures and lessons.

Examination modes

The course is examined by written exams. On the written exams and for the course, one of the following grades is assigned: Fail (U), Pass (G), Pass with distinction (VG). The grade is only set once all compulsory elements have been assessed.

A student who has been awarded a passing grade for the course cannot be reassessed for a higher grade. Students who do not pass a test or examination on the original date are given another date to retake the examination. A student who has sat two examinations for a course or a part of a course, without passing either examination, has the right to have another examiner appointed, provided there are no specific reasons for not doing so (Chapter 6, Section 22, HEO). The request for a new examiner is made to the Head of the Department of Mathematics and Mathematical Statistics. Examinations based on this course syllabus are guaranteed to be offered for two years after the date of the student's first registration for the course.

Credit transfer
All students have the right to have their previous education or equivalent, and  their working life experience evaluated for possible consideration in the corresponding education at Umeå university. Application forms should be adressed to Student services/Degree evaluation office. More information regarding credit transfer can be found on the student web pages of Umeå university, http://www.student.umu.se, and in the Higher Education Ordinance (chapter 6). If denied, the application can be appealed (as per the Higher Education Ordinance, chapter 12) to Överklagandenämnden för högskolan. This includes partially denied applications.

Other regulations

This course can not be included in a degree together with another course with similar contents. When in doubt, the student should consult the director of study at the department of mathematics and mathematical statistics.