Math 442 Assignments

General remarks

  1. 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.

  2.  
  3. 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.

  4.  
  5. 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 5th

Covering proof techniques frequently needed for the course

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

Assignment 2, due Thursday, January 12th

Covering classical problems

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

Assignment 3, due Thursday, January 19th

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

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

Assignment 4, due Thursday, January 26th

Covering Eulerian and Hamiltonian graphs, and applications

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

Assignment 5 due Thursday, February 2nd

Covering planarity, Euler's Theorem and inequalities

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

Assignment 6 due Thursday, February 16th

Covering polyhedra, duals and line graphs

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

Assignment 7, due Thursday, March 2nd

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

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

Assignment 8, due Thursday, March 9th

Covering the five colour theorem, face colouring, edge colouring

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

Assignment 9, due Thursday, March 16th

Covering scheduling problems, classical results on trees

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

Assignment 10, due Thursday, March 23rd

Covering spanning trees, Prufer sequences

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

Assignment 11, due Thursday, March 30th

Covering BFS and DFS, shortest paths, minimal spanning trees

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

Assignment 12, due Thursday, April 6th

Covering TSP, digraphs, max flow-min cut

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


Back to course home page.