Problems in Combinatorics and Graph Theory

✍ Scribed by Ioan Tomescu

• Publisher: Wiley-Interscience
• Year: 1985
• Tongue: English
• Leaves: 354
• Series: Wiley Series in Discrete Mathematics and Optimization
• Edition: 1
• Category: Library

✦ Synopsis

Covers the most important combinatorial structures and techniques. This is a book of problems and solutions which range in difficulty and scope from the elementary/student-oriented to open questions at the research level. Each problem is accompanied by a complete and detailed solution together with appropriate references to the mathematical literature, helping the reader not only to learn but to apply the relevant discrete methods. The text is unique in its range and variety -- some problems include straightforward manipulations while others are more complicated and require insights and a solid foundation of combinatorics and/or graph theory. Includes a dictionary of terms that makes many of the challenging problems accessible to those whose mathematical education is limited to highschool algebra.

✦ Table of Contents

Preface................................................................................. 6
Contents................................................................................ 8
Glossary of terms used.................................................................. 10
1 STATEMENT OF PROBLEMS................................................................. 20
1.1 COMBINATORIAL IDENTITIES........................................................ 22
1.2 THE PRINCIPLE OF INCLUSION AND EXCLUSION and INVERSION FORMULAS................. 29
1.3 STIRLING, BELL, FIBONACCI AND CATALAN NUMBERS................................... 34
1.4 PROBLEMS IN COMBINATORIAL SET THEORY........................................... 41
1.5 PARTITIONS OF INTEGERS.......................................................... 49
1.6 TREES........................................................................... 52
1.7 PARITY.......................................................................... 58
1.8 CONNECTEDNESS................................................................... 60
1.9 EXTREMAL PROBLEMS FOR GRAPHS AND NETWORKS....................................... 64
1.10 COLORING PROBLEMS.............................................................. 71
1.11 HAMILTONIAN PROBLEMS........................................................... 75
1.12 PERMUTATIONS................................................................... 77
1.13 THE NUMBER OF CLASSES OF CONFIGURATIONS RELATIVE TO A GROUP OF PERMUTATIONS.... 81
1.14 PROBLEMS OF RAMSEY TYPE........................................................ 84
2 SOLUTIONS............................................................................. 88
3 BIBLIOGRAPHY..........................................................................354