HW 2 comments

Max: 6.7
Min: 2.8
Average: 5.4
Median: 5.6
 
Comments:

B.  Only 4-5 people
got this correct.  Some mistakenly think that "any two vertices are joined by
exactly one simple path" means "every path in G is simple".  Some
assume G has two simple paths joining two vertices and prove there exists
a cycle (instead of the converse).  Some assume there is a cycle and then
claim that since a cycle is not simple, the given assumption is
contradicted.
 
C. Many students do not realize that the sum of degrees being even
is only a necessary condition for a graph with specified degree to
exist. They argue by using the degree condition to deduce the number
of edges and then say that since |A|+1=7, there is such a tree.
However, in general, the total "degree" being even does not imply
that there is a graph to start with, no to say "number of edges".
The best way to show existence is by construction.
 
D. In part b, some students try to specify a graph using set
notations. To this end, remember to write down both the vertex set
and the edge set, in the form (V,A).
 
G. Some claim that they could complete the proof by only considering
the case when the graphs are trees. This seems not very true since
the edge condition in the proposition does depend on the specific
graph we are considering. Some other students show only that the
proposition is true for the graph with single vertex, instead of
for any arbitrary graphs.