# MATA1410 Introduction to graph theory (4 cr)

**Study level:**

Intermediate studies

**Grading scale:**

0-5

**Language:**

English, Finnish

**Responsible organisation:**

Department of Mathematics and Statistics

**Curriculum periods:**

2024-2025, 2025-2026, 2026-2027, 2027-2028

## Description

Introduction to graph theory.

The contents roughly correspond to Harary: Graph Theory.

## Learning outcomes

After completing the course, the student

- knows the central theorems and definitions of graph theory, such as trees, bipartiate graphs, connectivity of graphs, and planar graphs .
- is familiar with the definitions of graphs, multigraphs, pseudographs, weighted graphs and digraphs.
- knows the definition of graph isomorphism and can recognize if the graphs are isomorphic by comparing their adjacency matrices and adjacency lists.
- can apply most important graph algorithms in solving problems related to different types of graphs.
- knows Eulerian graphs, Hamiltonian graphs, and the travelling salesman problem.
- is familiar with Euler's formula of planar graphs and Kuratowski's characterization theorem of planar graphs, and can apply these in studying and analyzing the properties of planar graphs.
- knows the chromatic number of a graph and coloring theorems of planar graphs.
- can apply induction in proving results in graphs theory.
- is familiar with the history of graph theory and some of its applications.

## Additional information

The course is organized every second year alternating with the course "Introduction to combinatorics". Introduction to graph theory will be taught in autumn 2024 and autumn 2026.

## Description of prerequisites

Good command of the long mathematics curriculum of high school. Courses "How to prove it?" and "Introduction to mathematics" are useful.

## Study materials

Lecture notes,

Harary: Graph Theory.

Trudeau: Introduction to Graph Theory,

Balakrishnan: Introduction to Discrete Mathematics,

Chartrand & Lesniak: Graphs & Digraphs,

Behzad, Chartrand & Lesniak-Foster: Graphs & Digraphs.

## Completion methods

### Method 1

**Evaluation criteria:**

Grade is based on weekly exercises and points from the exam.

Select all marked parts

### Method 2

**Evaluation criteria:**

Grade is based on the points from the final exam.

Select all marked parts

**Parts of the completion methods**

x

### Participation in teaching (4 cr)

**Type:**

Participation in teaching

**Grading scale:**

0-5

**Language:**

Finnish

#### Teaching

##### 9/2–10/27/2024 Lectures

##### 10/30–10/30/2024 Exam

##### 11/20–11/20/2024 Exam

x

### Exam (4 cr)

**Type:**

Exam

**Grading scale:**

0-5

**Language:**

English, Finnish