Comments on HW 2:

A--most people understood this, though some did not clearly label the
columns and rows; some relabeled the vertices with numbers, which was  a
little cumbersome.  Most people understood the problem, though.

B--a lot of people converted "any two vertices are joined by exactly one
simple path" to "all vertices...", not realizing that this actually changes
the problem considerably.  Also, some students were confused as to what "any
two vertices are joined by exactly one simple path" means.  Some reasoned
that  there was no simple path from a vertex to itself and thus no cycles.
Some people had difficulties writing down what it means for something not to
be a tree (either it's not connected, has a cycle, or both).  That is, they
had difficulties negating statements (which it seems haunted them again in
G).  Many people realized they needed to suppose there was a cycle and
derive a contradiction.

C--people did well on this, though were not very rigorous with a or c.  Many
people were using the TREE algorithm without realizing it (that is, V is a
tree at each step of the algorithm).  Realizing they were actually using the
algorithm in their argument could have helped them make it more rigorous.
Many others used the fact you used, however, which was good.  A handful of
people described in words their examples in b and d; I told them they needed
to draw them as well.

D--The most common mistake with part a was Adj^2 * Adj^4 = Adj^8.  Most
people understood b and c, though some didn't find all the cases for c.

E--Many people struggled with being rigorous for this problem.  That said,
most people understood the ideas involved.  For those that tried to be
explicit about the summations, many struggled with how to index the odd
degrees.  For example, I saw many \sum_{k=1}^n k(2m+1) to indicate the sum
of the degrees over vertices with odd degrees, when they meant to write
\sum_{k=1}^n (2 m_k + 1), where m_k is the degree of the ith vertex of odd
degree.

F--Many people understood this but did not show their work in b.

G--On this one, most people tried a proof by contradiction.
However, some of them arrived at a contradiction only for a specific
example.  Some thought the negation of
deg(u) >= 2|A|/|V| is  deg(u) <= 2|A|/|V|-1.