| |
| |
| |
| Introduction and basic concepts | |
| |
| |
| |
| An assortment of problems | |
| |
| |
| |
| Numbers and sets: notation | |
| |
| |
| |
| Mathematical induction and other proofs | |
| |
| |
| |
| Functions | |
| |
| |
| |
| Relations | |
| |
| |
| |
| Equivalences and other special types of relations | |
| |
| |
| |
| Orderings | |
| |
| |
| |
| Orderings and how they can be depicted | |
| |
| |
| |
| Orderings and linear orderings | |
| |
| |
| |
| Ordering by inclusion | |
| |
| |
| |
| Large implies tall or wide | |
| |
| |
| |
| Combinatorial counting | |
| |
| |
| |
| Functions and subsets | |
| |
| |
| |
| Permutations and factorials | |
| |
| |
| |
| Binomial coefficients | |
| |
| |
| |
| Estimates: an introduction | |
| |
| |
| |
| Estimates: the factorial function | |
| |
| |
| |
| Estimates: binomial coefficients | |
| |
| |
| |
| Inclusion-exclusion principle | |
| |
| |
| |
| The hatcheck lady & co. | |
| |
| |
| |
| Graphs: an introduction | |
| |
| |
| |
| The notion of a graph; isomorphism | |
| |
| |
| |
| Subgraphs, components, adjacency matrix | |
| |
| |
| |
| Graph score | |
| |
| |
| |
| Eulerian graphs | |
| |
| |
| |
| Eulerian directed graphs | |
| |
| |
| |
| 2-connectivity | |
| |
| |
| |
| Triangle-free graphs: an extremal problem | |
| |
| |
| |
| Trees | |
| |
| |
| |
| Definition and characterizations of trees | |
| |
| |
| |
| Isomorphism of trees | |
| |
| |
| |
| Spanning trees of a graph | |
| |
| |
| |
| The minimum spanning tree problem | |
| |
| |
| |
| Jarn�k's algorithm and Borůvka's algorithm | |
| |
| |
| |
| Drawing graphs in the plane | |
| |
| |
| |
| Drawing in the plane and on other surfaces | |
| |
| |
| |
| Cycles in planar graphs | |
| |
| |
| |
| Euler's formula | |
| |
| |
| |
| Coloring maps: the four-color problem | |
| |
| |
| |
| Double-counting | |
| |
| |
| |
| Parity arguments | |
| |
| |
| |
| Sperner's theorem on independent systems | |
| |
| |
| |
| An extremal problem: forbidden four-cycles | |
| |
| |
| |
| The number of spanning trees | |
| |
| |
| |
| The result | |
| |
| |
| |
| A proof via score | |
| |
| |
| |
| A proof with vertebrates | |
| |
| |
| |
| A proof using the Pr�fer code | |
| |
| |
| |
| Proofs working with determinants | |
| |
| |
| |
| The simplest proof? | |
| |
| |
| |
| Finite projective planes | |
| |
| |
| |
| Definition and basic properties | |
| |
| |
| |
| Existence of finite projective planes | |
| |
| |
| |
| Orthogonal Latin squares | |
| |
| |
| |
| Combinatorial applications | |
| |
| |
| |
| Probability and probabilistic proofs | |
| |
| |
| |
| Proofs by counting | |
| |
| |
| |
| Finite probability spaces | |
| |
| |
| |
| Random variables and their expectation | |
| |
| |
| |
| Several applications | |
| |
| |
| |
| Order from disorder: Ramsey's theorem | |
| |
| |
| |
| A party of six | |
| |
| |
| |
| Ramsey's theorem for graphs | |
| |
| |
| |
| A lower bound for the Ramsey numbers | |
| |
| |
| |
| Generating functions | |
| |
| |
| |
| Combinatorial applications of polynomials | |
| |
| |
| |
| Calculation with power series | |
| |
| |
| |
| Fibonacci numbers and the golden section | |
| |
| |
| |
| Binary trees | |
| |
| |
| |
| On rolling the dice | |
| |
| |
| |
| Random walk | |
| |
| |
| |
| Integer partitions | |
| |
| |
| |
| Applications of linear algebra | |
| |
| |
| |
| Block designs | |
| |
| |
| |
| Fisher's inequality | |
| |
| |
| |
| Covering by complete bipartite graphs | |
| |
| |
| |
| Cycle space of a graph | |
| |
| |
| |
| Circulations and cuts: cycle space revisited | |
| |
| |
| |
| Probabilistic checking | |
| |
| |
| Appendix: Prerequisites from algebra | |
| |
| |
| Bibliography | |
| |
| |
| Hints to selected exercises | |
| |
| |
| Index | |