Program Overview

Course Information

Course Description

The course SF2740 Graph Theory is a 7.5 credit course that covers basic concepts of graph theory, including degree, distance, diameter, matching, and more. The course also explores theory for matchings, structure theorems, minors, planarity, coloring, and random graphs.

Course Contents

The course covers the following topics:

• Basic concepts of graph theory: degree, distance, diameter, matching, etc.
• Theory for matchings, in particular for bipartite graphs
• Structure theorems about 2- and 3- connected components of graphs
• Mader's and Menger's Theorems
• Theory about minors, planarity
• Coloring of various kinds, Perfect graphs, Hadwiger's conjecture, random graphs and the probabilistic method

Intended Learning Outcomes

After completing the course, students should be able to:

• Explain basic concepts, theorems, and proofs within the parts of graph theory described by the course content
• Use basic concepts, methods, and theorems in graph theory to solve problems and communicate with the help of mathematical language

Literature and Preparations

Specific Prerequisites

• English B / English 6
• Completed basic course SF1610 Discrete Mathematics, SF1662 Discrete Mathematics, SF1679 Discrete Mathematics, or SF1688 Discrete Mathematics

Recommended Prerequisites

• Completed basic course in Discrete Mathematics

Literature

Information about course literature can be found in the course memo for the course offering or in the course room in Canvas.

Examination and Completion

Grading Scale

• A, B, C, D, E, FX, F

Examination

• TEN1 - Examination, 7.5 credits, grading scale: A, B, C, D, E, FX, F

Other Requirements for Final Grade

• Continuous examination with assignments and presentation of project

Examiner

• Katharina Jochemko

Ethical Approach

• All members of a group are responsible for the group's work
• In any assessment, every student shall honestly disclose any help received and sources used
• In an oral assessment, every student shall be able to present and answer questions about the entire assignment and solution

Further Information

Offered by

• SCI/Mathematics

Main Field of Study

• Mathematics

Education Cycle

• Second cycle