MATA1410 Introduction to graph theory (4 cr)

Introduction to graph theory.

The contents roughly correspond to Harary: Graph Theory.

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. 

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.

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

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.