User's name / E-mail address


I lost my password
Edition: 1th
Date: 2006
Page count: 300 pages
Format: B/5
ISBN: 978-963-9664-01-2
Category: in Hungarian and English
Series: Information Theory

Original price: 3400 Ft

Exercises in graph theory

Table of contents (shortened):

  1. Fundamental concepts of graph theory (isomorphism, degree sequences; trees, Cayley's theorem, Prüfer-code, minimal weight spanning tree; connectivity; directed graphs; miscellaneous exercises)
  2. Euler walks (existence of Euler walks, applications, variations of the problem)
  3. Hamiltonian paths and circuits (finding Hamiltonian paths and circuits, necessary conditions, sufficient conditions, misc. exercises)
  4. Planarity (Euler's formula; the theorems of Kuratowski, Fáry, and Wagner; duality, weak isomorphism, misc. exercises, related concepts)
  5. Matching (maximum and maximal matchings, bipartite graphs and Hall's condition, misc. Exercises; packing and covering)
  6. Flows, higher connectivity (flows in networks, edge- and vertex connectivity)
  7. Colouring (vertex colouring; edge colouring; perfect graphs; Mycielski's construction; list colouring)
  8. Matrix representations (adjacency matrix, its determinant and eigenvalues; incidence matrix; circuit and cut set matrices)
  9. 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.

Original price: 2200 Ft
Original price: 2600 Ft
Original price: 1750 Ft
Original price: 3600 Ft