SPRING SEMESTER 2009
MATH 475 - Graph Theory and Combinatorics
HOMEWORK ASSIGNMENTS.

Text Richard Brualdi Introductory Combinatorics

Section Problems Due
2.1 Basic counting principals 2.7.4 Feb. 18
2.2-2.3 Permutations and Combinations 2.7.2, 2.7.10, 2.7.17, 2.7.31 Feb. 18
2.4 Permutations of multisets 2.7.33 Feb. 18
2.5 Combinations of multisets 2.7.38, 2.7. 39 , 2.7. 45 Feb. 18
3.1 Pigeonhole principle 3.4.4, 3.4.9, 3.4.15 Mar. 2
3.2 Strong pigeonhole principle 3.4.14, 3.4.29 Mar. 2
3.3 Ramsey Theorem 3.4.23 Mar. 2
5.1-5.3 Binomial coefficients 9, 12, 18, 20, 22 Mar. 25
5.4 Multinomial theorem 29, 37, 39 Mar. 25
5.5 Newton's binomial theorem 46 Mar. 25
9.1, 9.2 Systems of distinct representatives 1, 2, 7, 9 Apr. 1
9.3 Stable marriages 19, 20, 22 Apr. 1
11.1 Basic properties of graphs 3, 5, 10, 11 Apr. 13
11.2 Eulerian trails 38 Apr. 13
11.3 Hamiltonian cycles 39 Apr. 13
11. 4 Bipartite graphs 47, 48 Apr. 20
11.5 Trees 53, 55, 57 Apr. 20
11.7 Tree algorithms 80, 82, 84 Apr. 20
13.1 Digraphs 3, 22 Apr 29
13.2 Networks 24 Apr 29
13.3 Matchings 29 Apr 29
6.1-6.4 Inclusion exclusion formula 3, 5, 9, 15, 24 May 11