Description

Instruction
This is a written assignment and is worth 30% of the marks for individual assignments. Please type your answers or write in legible handwriting. Answers that are messy and hard to read will be deducted marks.
Part A) Proof by Induction (9 points)
Prove that on a n×n chessboard, there is a rook’s tour that starts from the top-left corner and ends at the bottom-left corner.
Hint:
B Definitions of a rook’s tour and rook’s move can be found on page 234 in the textbook. B As we learned in class, sometimes we need to prove a more general claim.
Part B) Graph Theory: Edges and Density of a Graph (9 points)
Answer Questions 11.36, 11.37, and 11.38 (Page 602, textbook)
Part C) Graph Theory: Modelling (9 points)
Answer Questions 11.54 – 11.55 (Page 603, textbook)
Hint:
B It helps to study Example 11.14 in the textbook in. It is also interesting to know that the answer to Question 11.54 is in fact the “intersection dimension/intersection number” of the graph.
Part D) Graph Theory: Connectedness and Connected Components (3 points)
Do Question 11.95 (Page 620, textbook)
B If you are disproving the claim by a counterexample, how many connected components are there in your counterexample?
1