Exercises in graph theory

Authors O. I. Mel'nikov, Vladimir I. Sarvanov, Regina Iosifovna Tyshkevich, V. A. Emelichev, I.È. Zverovich

Publication date 19 April 1998

Problem books (00A07) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics (05-01) Graph theory (05Cxx)

Review text

Imagine a river with its two banks being Applications (A) (incl. those in mathematics!) and Discrete Mathematics (DM) together with some bridges joining the banks of this imaginary river and providing intense exchange between them. Here, (A) provides problems and need for new models and algorithms, but the role of (DM) is to unify ideas, models and to create methods useful for mathematical treatment and solution of these problems. In this picture, Graph Theory (GT) can be viewed as a territory surrounding several bridges in a rich DM-riverside area that has been increasingly effective during the last 40 years. Starting from the great touch (1736) of L. Euler of the question about Seven Bridges (in Königsberg, over the river called Pregel) GT has grown into an important part of mathematics. From its early days GT has been connected with several parts of mathematics. Firstly, with topology of linear complexes -- after investigations of L. Euler (1752) and by A.-L. Cauchy (1813) on Euler's polyhedral formula, this link took its shape due to ideas in J. B. Listing's ``Der Census räumlicher Complexe (1861) and through the work of H. Poincaré (at the turn of the century) on Euler characteristics. All this was documented with a section on graphs in the article ``Analysis Situs by M. Dehn and P. Heegaard (1907) [Encyclopädie der Mathematischen Wissenschaften, 1898-1935, III AB3, 153-220]. Secondly, with linear algebra -- by explicitly extracting analogies between a bunch of notions concerning vector spaces and those concerning graphs. It started with G. Kirchhoff's idea (1845) of fundamental set of circuits. Thereafter came O. Veblen's spanning trees and H. Whitney's axiomatisation (1935) of properties of rank functions and it gave rise to the matroid theory. Later developedments in matroid theory have had a remarkable influence on linear algebra as well. Thirdly, with invariant theory studies of regular graph factorizations and -- in connection with a question of D. Hilbert -- J. Petersen's (1891) originative application of methods and notation of GT to invariants. Recall also R. G. Swan's wonderful idea to use graphs for proving Amitsur and Lewitzki's theorem and developments thereafter; see [Proc. Am. Math. Soc. 14, No. 3, 367-373 (1963; Zbl 0118.01802)], also in \textit{B. Bollobás} [Graph theory. An introductory course (1979; Zbl 0411.05032)]. Fourthly, with group theory -- by the yet unsolved D. König's problem of finding conditions necessary and sufficient for a permutation group on a given set \(V\) to be graphical. In other words, the problem stands to find a criterion for a subgroup in the symmetric group on \(V\) to be the automorphism group of some graph with \(V\) as its vertex set. It occurs to the reviewer also an idea heard in the lectures on permutation groups by D. A. Suprunenko (in Minsk, in early eighties). Namely, observing that finite groups of odd order are just the automorphism groups of finite tournaments, it becomes attractive to attempt to better understand and to use in GT this link -- through the proof of Thompson and Feit's theorem (1962) -- between soluble groups and digraphs. A striking link between graphs and groups appears in the book by \textit{A. Yu. Ol'shanskij} [Geometry of defining relations in groups (1991; Zbl 0732.20019 and Zbl 0676.20014)]. Fifthly, with hypergraphs and matching theory -- D. König's work on \((k,k)\)-correspondences resulted in a positive answer (1914; published 1923) to the question, whether every regular bipartite graph has a 1-factor. Investigations of correspondences together with J. König's (D.K.'s father!) idea of their graphical representation prepared ground for Ph. Hall's Marriage Theorem (1935) and striking developments thereafter. Sixthly, with colouring maps on surfaces and matroid theory -- thoughts that had started with De Morgan's student F. Guthrie's 4-colour conjecture (1852) have reached at Robertson and Seymour's theory of excluded minors and their proof of Hadwiger's conjecture and also, at the Critical Problem -- this last remaining unsolved; see \textit{H. H. Crapo} and \textit{G.-C. Rota} [On the foundations of combinatorial theory: Combinatorial geometries. M.I.T. Press (1970; Zbl 0216.02101)]. Numerous results that prepare the reader to follow the above ideas are clearly exposed in the book [[L]: Lectures on graph theory. B.I.-Wissenschaftsverlag, Mannheim (1994; Zbl 0865.05001)] written by the first four authors of the book [E] under review. In order to introduce GT to students several people (including the reviewer) use the book [[W]: \textit{R. J. Wilson}, Introduction to graph theory. Oliver and Boyd (1972); 4th edition, Longman Group Ltd. (1996; Zbl 0891.05001)] -- for its good taste in choice of both the topics and the theorems to be understood first and also, for successful exercises to each chapter in [W]. In fact, numerous textbooks of GT have modest lists of exercises, so admitting importance of problem solving for those learning GT. However, it can often be that after having [W] successfully finished, students in mathematics and mathematically inclined students in computer science feel it necessary to broaden and deepen their knowledge of GT in a systematic way before starting to read texts like [\textit{J. Friedman}, ed., Expanding graphs. DIMACS. Series in Discrete Mathematics and Theoretical Ccomputer Science, vol. 10 (1993; Zbl 0777.00033)] or [\textit{W. Tutte}, Graph theory as I have known it. Clarendon Press (1998)], recent papers on enumeration of graphical partitions or surveys like that by \textit{C. St. J. A. Nash-Williams} [Bull. Lond. Math. Soc. 14, 177-212 and 294-328 (1982; Zbl 0487.05020 and Zbl 0492.05024)], and last but not least -- before feeling able to enjoy solution (or the given solutions!) of the problems in [\textit{L. Lovász}, Combinatorial problems and exercises (1979; Zbl 0785.05001)]. For such people (but far from only for them!) the books [L] and [E] serve good, supporting their efforts just at the needed level. The authors of these books have been researchers and have teached GT and/or DM for a long time. Therefore, joining their forces has resulted in the books both attractive and useful, with both pure and applied trends in graph theory being stressed. The two books match nice in their contents, notation and terminology. The main concern here is [E]. It contains more than a thousand of exercises that are grouped into 11 chapters: ABC of graph theory; trees; independence and covering; connectivity; matroids; planarity; graph transversals; degree sequences; graph colourings; digraphs; hypergraphs. Each chapter is divided into several sections. Each section includes definitions, examples, even conjectures and explanations are given of relations between the notions used in exercises in the particular section. Several results useful for solving exercises in the section are given also -- a kind of general hint for solvers. Proofs are omitted -- they can be found in [L]. The authors often use figures to illustrate their exposition, so helping the reader to understand quicker GT results. In [E] there are also exercises linked together into chains. Solving them offers the reader an additional chance to deepen knowledge of GT. The above constitutes the first half of the book [E] -- its pages 1-182. Its second half (pages 183-339) contains answers, hints or full solutions to all exercises. These solutions vary from few lines to two pages per given exercise. Numerous exercises in [E] are collected in book form for the first time. Nevertheless, their choice is balanced and presentation is clear which makes them useful for anyone with real interest in GT. Readers of [E] have Index of notions (9 pages) and List of notations (4 pages) as well. On the whole, [E] contains plenty of interesting mathematics that belongs to or is related to GT and so enables a good training. However, one regrets that in order to minimize the length there have not been included chapters on algebraic and combinatorial GT or on graph isomorphisms, also no sections on networks or on stable matchings. Recent deep results and numerous links of GT with other parts of mathematics convince us that the best days for GT are far from being over. G.-C. Rota writes: ``Graph theory shares a unique distinction with perhaps only one other branch of mathematics, namely number theory; in both fields we find an unusually high ratio of nontrivial theorems to definitions. See [Discrete Math. 153, No. 1-3, 289-303 (1996; Zbl 0855.05001)]. The role of GT as a member of the DM-family is splendidly exposed in the book [\textit{J. H. van Lint} and \textit{R. M. Wilson}, A course in combinatorics. Cambridge University Press (1992; Zbl 0769.05001); reprinted 1994 and 1996]. Concerning applications of graph theory to other areas of mathematics see also [\textit{L. W. Beineke} and \textit{R. J. Wilson} (eds.), Graph connections (1997; Zbl 0862.00008)]. Therefore, it is quite likely that new editions of [L] and/or [E] will appear soon. In such a case it becomes possible also to correct misprint of `Ferrer' instead of `Ferrers' and a few others. Note once more that high-quality learning (teaching) of mathematics needs an active style -- reading (using) of good text(s) must be balanced with extensive enough and serious problem solving. For such possibility existing in the case of GT provided by [L] and [E] -- seldom it is the case in GT that the textbook and the exercise book have been written by the same authors -- a lot of people are grateful to the authors of [L] and [E] for their effort.

Recommendations

Cited in

(12)

This page was built for publication: Exercises in graph theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4385570)