The main aim of this course is to present to the students some basic results and proof techniques in graph theory, in particular in connection with graph theoretic algorithms and with electrical networks.

• combine fundamental graph theoretic concepts and results to answer questions concerning the structure of graphs
• find distances, number of shortest paths, minimal spanning trees, and minimal walks through all edges
• find maximal flows and minimal cuts, critical and optimal edges
• find maximal matchings and minimal coverings in bipartite graphs, find maximal job assignments and optimum scheduling
• calculate Pauling bonds in benzoids
• apply current spaces and voltage spaces and Kirchhoff's tree theorem to find currents and voltages and driving point resticances in electrical networks
• calculate resistances in connection with random walks (Markov processes)
• apply Euler's formula to planar graphs

Basic graph theory, including Euler graphs, Menger's theorem on connectivity, planarity, matchings with applications to structure rank, scheduling problems, and Pauling bonds in benzoids. Network flows which constitute the foundation of combinatorial optimization with applications in e.g. operations research. Description and complexity of algorithms (shortest paths, spanning trees of minimal weight, the Chinese Postman's problem, maximum matchings, job assignment) of interest in computer science. The mathematical foundation of electrical networks, including effective resistances expressed by spanning trees and determinants. Random walks. Planar graphs.