# 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 full details, with citations from the
notes or homework. 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, and with as
much detail as the class notes including all the verbal
descriptions. In summary, show all your working to get full marks.

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

Covering proof techniques frequently needed for the course

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

#### Assignment 2, due Thursday, January 11th

Covering classical problems

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

#### Assignment 3, due Thursday, January 18th

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

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

#### Assignment 4, due Thursday, January 25th

Covering Eulerian and Hamiltonian graphs, and applications

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

#### Assignment 5 due Thursday, February 1st

Covering planarity, Euler's Theorem and inequalities

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

#### Assignment 6 due Thursday, February 15th

Covering polyhedra, duals and line graphs

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

#### Assignment 7, due Thursday,
March 1st

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

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

#### Assignment 8, due Thursday,
March 8th

Covering the five colour theorem, face colouring, edge colouring

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

#### Assignment 9, due Thursday,
March 15th

Covering scheduling problems, classical results on trees

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

#### Assignment 10, due Thursday,
March 22nd

Covering spanning trees, Prufer sequences

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

#### Assignment 11, due Thursday,
March 29th

Covering BFS and DFS, shortest paths, minimal spanning trees

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

#### Assignment 12, due Thursday,
April 5th

Covering TSP, digraphs, max flow-min cut

Problems
67, 68, 69, 70, 71, 72

Back
to course home page.