Table of contents (shortened):
- Fundamental concepts of graph theory (isomorphism, degree sequences; trees, Cayley's theorem, Prüfer-code, minimal weight spanning tree; connectivity; directed graphs; miscellaneous exercises)
- Euler walks (existence of Euler walks, applications, variations of the problem)
- Hamiltonian paths and circuits (finding Hamiltonian paths and circuits, necessary conditions, sufficient conditions, misc. exercises)
- Planarity (Euler's formula; the theorems of Kuratowski, Fáry, and Wagner; duality, weak isomorphism, misc. exercises, related concepts)
- Matching (maximum and maximal matchings, bipartite graphs and Hall's condition, misc. Exercises; packing and covering)
- Flows, higher connectivity (flows in networks, edge- and vertex connectivity)
- Colouring (vertex colouring; edge colouring; perfect graphs; Mycielski's construction; list colouring)
- Matrix representations (adjacency matrix, its determinant and eigenvalues; incidence matrix; circuit and cut set matrices)
- Complexity theory (paths and circuits; colouring and cliques; decision problems and search problems; misc. exercises)
The book contains about 500 problems in these topics, with full solutions. The famous book "Combinatorial problems and exercises" (Lovász, 1979) is still the best for graduate and postgraduate math majors but most of its problems are too difficult for undergraduates. Most of the existing English undergraduate texts contain some exercises but usually without solutions. The novelty of this book is that
1. it contains mostly "easy" problems which can be solved by any undergraduate who understands the definitions and knows the most basic theorems and methods,
2. it covers only those chapters of graph theory which are needed for engineering students as well (for other important chapters of graph theory like Ramsey theory, infinite graphs etc. the readers are referred to other sources), and
3. it contains full solutions with as many details as required for typical undergraduate exams.
This collection is based on the discrete mathematics courses we offer since 1985 for the undergraduate electric engineering majors and informatics majors at the Budapest University of Technology and Economics. Most problems have been tested by dozens of TA-s (and by thousands of students) in the last two decades.