Comments on HW:

Question 2 was graded fully. The other two questions were graded for
completeness.

2(i): -Several students used part (ii) of Exercise 2 is to prove part
(i). Remember to prove the exercises in order. You can use earlier
exercises to prove later ones, but not the other way
around. Otherwise, your logic that both (i) and (ii) are correct is
circular. Since (i) implies (ii) and (ii) implies (i), they are
equivalent statements, but even if you can prove that two statements
are equivalent, doesn't mean they are both correct.  -One common
argument was to argue by induction that if you have a tree T on n-1
nodes, then attaching an extra node to the tree by an edge preserves
the property that it has at least 2 leaves. In order to get full
point, you need to first argue that every tree on n nodes can be
constructed this way. Then you need to analyze all possible ways of
attaching an extra node: it could either attach to a node with degree
at least 2 or it could attach to a leaf, and the effect on the number
of leaves is different in each case (either it goes up by one or stays
the same).  -Another common argument is to take a path in the tree T
with maximum length and argue that both endpoints of the path are
leaves. If you proceed this way, you need to use the fact that T is
acyclic to argue that the endpoints are distinct and are both leaves.

2(ii): -This problem was to prove that any tree on n nodes has n-1
edges, not just spanning trees of a connected graph G. If you
proceeded by induction to prove that every spanning tree of a
connected graph G on n nodes has n-1 edges, you need to be careful in
your inductive step. Specifically, if 1 is a node in G, then the
smaller graph G' = G\{1} may not be connected. In order to apply the
inductive hypothesis correctly, you would have to apply it on each
connected component of G' in order to get the result that any spanning
tree on G has n-1 edges.

2(iii): -There were many solutions that were suspiciously similar to a
StackExchange post.  -Many students obtained an inequality like sum_{v
in V} deg(v) >= 3(n/2)+(n/2). In order to get full points, you need to
justify this inequality.