Suggested Problems
Chapter 1
Exercises: 2, 3, 10, 11, 15, 18, 20, 21
Chapter 2
Exercises: 1, 2, 4, 5, 8, 11, 12
Chapter 3
Exercises: 1, 2, 3, 4, 5, 7, 9, 10, 11, 14, 15
Chapter 4
Exercises: 1, 3, 4, 5, 8, 9, 11, 12, 13, 18, 20, 24, 27, 28, 30, 32
Chapter 5
Exercises: 2, 3, 6, 7, 10, 11, 16, 19
Chapter 7
Exercises: 1, 2, 3, 4, 5, 11, 15, 16, 17, 18
Chapter 9
Exercises: 6, 8, 12
Chapter 10
Exercises: 1, 2, 4, 5, 6, 7, 11
Chapter 11
Exercises: 1, 2, 3, 7, 12
Additional problems
- Let G be a graph on n vertices with edgeset E. Show that for any partition E = E1 ∪ E2 ∪… ∪ En into non-empty subsets there exists a cycle containing at most one edge from each Ei.
- Let G be a directed graph on n vertices with edgeset E. Show that for any partition E = E1 ∪ E2 ∪… ∪ En into non-empty subsets there exists a directed cycle containing at most one edge from each Ei.
- Let G be a k-regular bipartite graph. Show that the edgeset can be partitioned into k parts E1 ∪ E2 ∪… ∪ Ek such that each Ei is a complete mathcing.