Graph Theory

How can relationships, connections, and structures be described mathematically? Graph theory provides a powerful and unified language for answering such questions. It connects fundamental mathematical ideas with computer science and a wide range of applications.

This textbook provides a systematic introduction to graph theory, beginning with the basic concepts of graphs, vertex degrees, paths, cycles, and connectivity. It develops trees and forests, bipartite graphs, matchings, and Menger's theorem, before turning to planar graphs and Kuratowski's theorem, graph colorings, network flows, and Hamiltonian cycles. The final chapters focus on subgraphs, graph minors, tree decompositions, and treewidth.

Throughout the book, clear definitions, complete proofs, and illustrative figures are used to develop a precise understanding of the mathematical structures underlying graph theory. Numerous exercises with detailed solutions reinforce the material and make the book suitable both for guided university study and independent learning.

The book is intended particularly for students of mathematics and computer science taking a first university-level course in graph theory, but also for anyone wishing to study the subject systematically and rigorously. An outlook at the end of the book introduces further topics, including Ramsey theory, random graphs, and modern graph minor theory.