Index

• 0-1 incidence matrix §12.1
• adjacency matrix Definition 2.36
• affine plane §9.6
• anti-chain §5.1
• augmenting path Definition 6.21
• automorphism Definition 2.13
• averaging principle §2.2
• basic notions Definition 2.21
• Berge theorem Theorem 6.23
• binary relation §5.1
• Birkhoff-von Neumann theorem §6.2
• blocking set §9.5
• catalan numbers §10.3
• Cauchy-Binet formula §12.3
• Cayley graphs Example 2.2
• Cayley’s formula Theorem 4.5
• chain §5.1
• chromatic index Definition 11.12
• chromatic number §11.1, Definition 11.1
• chromatic polynomials §11.2
• coloring Definition 11.1
• Complete graph Example 2.1
• connected components §2.3
• cover Definition 6.13
• cut-edge Definition 4.12
• cut-vertex Definition 4.12
• cycle Definition 2.29
• decreasing subsequence §5.1
• Degree 5th item
• deletion-contraction principle Proposition 11.3
• design Chapter 9
• diameter §2.5
• Dilworth’s decomposition theorem Chapter 8
• Dilworth’s theorem Theorem 5.2
• Directed graphs Remark 1.3
• Dirichlet’s theorem Theorem 5.14
• double-counting §2.2
• doubly stochastic matrix §6.2
• edge connectivity §7.2
• edge-chromatic number §11.4
• elementary subgraph §12.4
• embedding Definition 13.1
• equivalences to Hall’s theorem §6.10
• Erdös-Gallai Theorem Theorem 6.30
• Erdös-Szekeres lemma Theorem 5.1
• Euclidean Lattices Example 2.5
• Euler’s formula Theorem 13.5
• Euler’s theorem Theorem 3.3
• Eulerian graph Definition 3.1
• exponential generating function Chapter 10
• f-factor Definition 6.26
• faces Definition 13.2
• factor Definition 6.6
• fano plane Example 9.1
• Fisher’s inequality §8.3
• flow Definition 7.1
• Ford-Fulkerson Algorithm Remark 7.7
• Forests Definition 4.1
• Gale-Shapley algorithm §6.7
• Gallai theorem Theorem 6.20
• girth §5.2
• Graph Definition 1.1
• graph dual §13.3
• Graph invariant 2nd item
• graph metric Exercise* 2.43
• graph minor §13.1
• Graph property 1st item
• Growth of groups Question 2.48
• hadamard matrix §9.7
• Hall’s marriage theorem Theorem 6.2
• history §1.2
• homomorphism Definition 2.13
• incidence matrix Definition 12.1, §2.2
• increasing subsequence §5.1
• independent sets Definition 6.13
• induced subgraph Exercise 2.16
• intersecting set systems §8.2
• Intersection graph Example 2.3
• isolated 6th item
• isomorphism Definition 2.13
• Kirchoff’s matrix tree theorem Theorem 12.13
• Kirchoff’s node law item 2
• Konig-Egervary theorem Theorem 6.17
• Kuratowski’s theorem §13.1
• Laplacian matrix §12.2
• latin rectangle §6.2
• linear algebra method §8.3
• linear spaces §9.3
• Mantel’s theorem Lemma 5.6
• matching Definition 6.1
• matroid §11.5
• max-flow min-cut theorem Theorem 7.3
• Menger’s theorem §7.3
• Minimal Spanning Tree Definition 4.17
• Minimal spanning tree algorithms §4.4
• Multi-graphs Remark 1.3
• Neighbourhood 4th item
• non-intersecting set systems §8.2
• number theory §5.4
• ordinary generating function Chapter 10
• partial order §5.1
• Path Definition 2.29
• perfect matching Definition 6.1
• permutation matrix §6.2
• planar graph Chapter 13
• planted plane tree 2nd item
• polyominoes Example 10.7
• poset Chapter 8
• probabilistic method §5.3
• projective plane §9.4
• Prufer code §4.1
• Ramsey numbers §5.3
• random spanning trees §4.5
• Read’s conjecture Question 11.15
• Real-life graphs §1.1.1
• Regular graph 7th item
• Rota-Welsh conjecture §11.5
• Ryser’s theorem Theorem 6.11
• SDR Definition 6.8
• self-avoiding walks Example 10.5
• set systems Definition 2.23
• Shannon rate §6.8
• Spanning subgraph 3rd item
• spanning trees §4.2
• Sperner’s theorem Theorem 8.3
• Stable matching §6.7
• Steiner system Chapter 9
• symmetric design Chapter 9
• trail Definition 2.29
• tree counting theorem Theorem 4.6
• Tree counting via Laplacians Corollary 12.12
• Trees Definition 4.1
• triangulation §13.1
• Turan’s theorem Theorem 5.7
• Tutte’s factor theorem Theorem 6.24
• vertex connectivity §7.2
• Wagner’s theorem Theorem 13.7
• walk Definition 2.29