6.042 Midterm 3 Rubrics

Problem 1 (15 points)
5 points for each part
(a) 2.5 for each antichain
(b) 2.5 if wrote "max chain size" but the wrong number

Problem 2 (20 points)
5 points for (a), 15 points for (b)
(a) 2-3 points for defining equivalence but wrong relation
(b) 12 points for slightly off
    5-7 points for some argument, but hand-wavy

Problem 3 (20 points)
5 points for (a), 15 points for (b)
(a) if correct example
(b) 5 points if only did the case where the two paths don't share any vertices (i.e. u -> v -> u is a cycle)

Problem 4 (20 points)
3 points for general induction structure (induction hypothesis, base case(s), inductive step and conclusion exist)
2 points for correctly formulated induction hypothesis
(if inducting on n, 1 point out of 2)
3 points for correct base case(s)
10 points for inductive step
-3 if just added a node to the m-vertex graph, without proving that all m+1-vertex graphs are made this way (e.g. by taking a graph, removing a vertex, and adding it back. or by saying that the vertex must be a leaf)
7 points for rest of proof, that the next vertex can be one of n-1 colors
if inducting on n, may receive 2-3 points for some coherent argument
1 point for stating any "fun fact about trees" if rest of proof is incorrect

Problem 5 (15 points)
-5 points for each incorrect part (down to 0)

Problem 6 (10 points)
(a) 3 points
(b) (i) 2 points
    (ii) 1 point
    (iii) 1 point
    (iv) 1 point
    (v) 2 points
In each part, 0.5 for incorrect but some logical explanation