|
1 Introduction and basic concepts |
|
|
1 | (46) |
|
1.1 An assortment of problems |
|
|
2 | (5) |
|
1.2 Numbers and sets: notation |
|
|
7 | (9) |
|
1.3 Mathematical induction and other proofs |
|
|
16 | (9) |
|
|
25 | (7) |
|
|
32 | (4) |
|
|
36 | (4) |
|
|
40 | (7) |
|
|
47 | (50) |
|
2.1 Functions and subsets |
|
|
47 | (5) |
|
2.2 Permutations and factorials |
|
|
52 | (3) |
|
2.3 Binomial coefficients |
|
|
55 | (11) |
|
2.4 Estimates: an introduction |
|
|
66 | (7) |
|
2.5 Estimates: the factorial function |
|
|
73 | (8) |
|
2.6 Estimates: binomial coefficients |
|
|
81 | (5) |
|
2.7 Inclusion-exclusion principle |
|
|
86 | (5) |
|
2.8 The hatcheck lady & co. |
|
|
91 | (6) |
|
3 Graphs: an introduction |
|
|
97 | (41) |
|
3.1 The notion of a graph; isomorphism |
|
|
97 | (9) |
|
3.2 Subgraphs, components, adjacency matrix |
|
|
106 | (6) |
|
|
112 | (5) |
|
|
117 | (6) |
|
3.5 An algorithm for an Eulerian tour |
|
|
123 | (4) |
|
3.6 Eulerian directed graphs |
|
|
127 | (5) |
|
|
132 | (6) |
|
|
138 | (29) |
|
4.1 Definition and characterizations of trees |
|
|
138 | (6) |
|
|
144 | (7) |
|
4.3 Spanning trees of a graph |
|
|
151 | (4) |
|
4.4 The minimum spanning tree problem |
|
|
155 | (6) |
|
4.5 Jarnik's algorithm and Boruvka's algorithm |
|
|
161 | (6) |
|
5 Drawing graphs in the plane |
|
|
167 | (35) |
|
5.1 Drawing in the plane and on other surfaces |
|
|
167 | (7) |
|
5.2 Cycles in planar graphs |
|
|
174 | (7) |
|
|
181 | (10) |
|
5.4 Coloring maps: the four-color problem |
|
|
191 | (11) |
|
|
202 | (21) |
|
|
202 | (9) |
|
6.2 Sperner's theorem on independent systems |
|
|
211 | (7) |
|
6.3 A result in extremal graphy theory |
|
|
218 | (5) |
|
7 The number of spanning trees |
|
|
223 | (17) |
|
|
223 | (1) |
|
|
224 | (2) |
|
7.3 A proof with vertebrates |
|
|
226 | (3) |
|
7.4 A proof using the Prufer code |
|
|
229 | (2) |
|
7.5 A proof working with determinants |
|
|
231 | (9) |
|
8 Finite projective planes |
|
|
240 | (22) |
|
8.1 Definition and basic properties |
|
|
240 | (10) |
|
8.2 Existence of finite projective planes |
|
|
250 | (5) |
|
8.3 Orthogonal Latin squares |
|
|
255 | (3) |
|
8.4 Combinatorial applications |
|
|
258 | (4) |
|
9 Probability and probabilistic proofs |
|
|
262 | (32) |
|
|
262 | (7) |
|
9.2 Finite probability spaces |
|
|
269 | (10) |
|
9.3 Random variables and their expectation |
|
|
279 | (6) |
|
|
285 | (9) |
|
|
294 | (39) |
|
10.1 Combinatorial applications of polynomials |
|
|
294 | (4) |
|
10.2 Calculation with power series |
|
|
298 | (11) |
|
10.3 Fibonacci numbers and the golden section |
|
|
309 | (8) |
|
|
317 | (5) |
|
|
322 | (1) |
|
|
323 | (3) |
|
|
326 | (7) |
|
11 Applications of linear algebra |
|
|
333 | (30) |
|
|
333 | (5) |
|
|
338 | (4) |
|
11.3 Covering by complete bipartite graphs |
|
|
342 | (3) |
|
11.4 Cycle space of a graph |
|
|
345 | (4) |
|
11.5 Circulations and cuts: cycle space revisited |
|
|
349 | (4) |
|
11.6 Probabilistic checking |
|
|
353 | (10) |
Appendix: Prerequisites from algebra |
|
363 | (8) |
Bibliography |
|
371 | (6) |
Hints to selected exercises |
|
377 | (22) |
Index |
|
399 | |