# Math 442 Assignments

###
General remarks

- Homework should be legible and neat, questions should be answered
in order, and pages should be fastened
with
a staple with your name and student number on at least the
front page in pen.

- Homework will be collected on Thursdays at the start of
class and will
cover
the material
through Tuesday's lecture (roughly). You should start attempting the
problems
as soon as possible after the material is presented in lecture. Please
don't save it all for Wednesday night.

- Solutions should be written carefully, using good English,
complete sentences,
and adequate detail, with citations from the book
or notes. Some of these solutions will be explanatory proofs. A good
guideline
here is that you should write proofs the way you would like to see them
in your textbook. In summary, show
all your working to get full marks.

#### Assignment 1, due Thursday, January 15th

Covering classical problems

Problems
1, 2, 3, 4, 5, 6

#### Assignment 2, due Thursday, January 22nd

Covering basic theory, complement, isomorphism, representations and
types of graphs

Problems
7, 8, 9, 10, 11, 12

Assignment 3, due Thursday, January
29th

Covering Eulerian and Hamiltonian graphs, and applications

Problems
13, 14, 15, 16, 17, 18

Assignment 4, due Thursday, February
5th

Covering planarity, Euler's Theorem and inequalities

Problems
19, 20, 21, 22, 23, 24

Assignment 5, due Thursday, February
26th

Covering polyhedra, duals and line graphs

Problems
25, 26, 27, 28, 29, 30

Assignment 6, due Thursday, March 5th

Covering colouring, the chromatic polynomial and number,
deletion-contraction

Problems
31, 32, 33, 34, 35, 36

Assignment 7, due Thursday, March 12th

Covering the five colour theorem, face colouring, edge colouring

Problems
37, 38, 39, 40, 41, 42

Assignment 8, due Thursday, March 19th

Covering scheduling problems, classical results on trees

Problems
43, 44, 45, 46, 47, 48

Assignment 9, due Thursday, March 26th

Covering spanning trees, Prufer sequences

Problems
49, 50, 51, 52, 53, 54

Assignment 10, due Thursday, April 2nd

Covering BFS and DFS, shortest paths, minimal spanning trees

Problems
55, 56, 57, 58, 59, 60

Assignment 11, due Thursday, April 2nd

Covering TSP, digraphs, max flow-min cut

Problems
61, 62, 63, 64, 65, 66

Back to
course
home page.