General comment 0

Students should go back to some of my previous homework summaries and read the general comments there, since I saw some of the same mistakes cropping up again in this assignment.

General comment 1

Sometimes students will write up "false starts" in their proofs, i.e. attempt to argue one way, explain why the approach fails, before stating a workable approach. This may be helpful to their thinking while working out the proof, but it is usually worse than useless in the final write-up -- it only provides opportunity to lose points, while contributing nothing to the proof itself. I recommend leaving such sections out of the final write-up.

General comment 2

Sometimes a student will state in their proof that a particular case is "the worst case" and then only provide a proof for this case, while never specifying in what sense this case is "worst" or why other cases can be ignored or reduced to this case. I usually mark down such vagueness. To properly use this technique, you need to be very specific about what you mean by "worst", by some measurable or deterministic criterion, and you need to make it very clear how other cases are handled.

General comment 3

In general, you should state when you are invoking theorems, lemmas, and corollaries in your proofs. I was fairly lenient on this assignment, but in problem 4 I did mark down for not mentioning Euler's Theorem.

General comment 4

Sometimes students will say something like "The graph G is still connected after we remove vertex v." We may say this informally in conversation or discussion as a sort of "slang" or shorthand, but it is bogus in a formal write-up (such as a homework assignment). The graph G is still the graph G, and its properties do not change. You are really trying to say something about the NEW graph obtained from G, not about G itself. What you want to say is something like, "The graph obtained from G by removing v (usually denoted G\v or G-v or G-{v}) is connected." This advice applies whenever you are making constructions in your proof, defining or deriving new graphs from old ones, by adding or deleting edges and/or vertices. It is often handy to give the new graphs names (G', G'', G~, etc.). Along with this advice, when you have several graphs floating around in your proof, typically sharing some set of vertices or edges, you need to always be specific about which graph you are referring to when referring to things like "the degree of vertex v", or "paths from x to y", etc, because they usually defined with respect to some graph. For example, if H is a subgraph of G and v is a vertex of H, then the term "degree of v" is ambiguous. The degree of v in H may be different from its degree in G. Don't make the reader have to guess which context you mean.

Terminology

in the chapter on trees, the text does have sections on minimum spanning trees and rooted trees. However, none of the problems in this homework set make any use of these concepts. Thus it did not make sense to speak of minimum spanning trees (in the absence of an edge-cost function), rooted trees, or children of vertices (in a tree without a designated root). One can always turn a tree into a rooted tree by choosing some vertex to be the designated root, but in general this choice is not canonical, so for general tree it makes no sense to talk about THE root or to talk about "children of a vertex".

Regarding problems 1 and 2

Most students solved these problems just fine. A few neglected to account for overcounting when counting via permutations, either by ignoring choice of starting vertex in the cycle, or by ignoring the two directions of a cycle.

Regarding problem 3

Common problems here fell into several categories:

Some claimed that (the contrapositive of) Theorem 9.5 says that IF a graph has a Hamiltonian cycle, THEN all vertex degrees must be at least half the total number of vertices. This is false (consider a graph which is just a cycle on 5 or more vertices). The theorem provides a SUFFICIENT condition, NOT a NECESSARY condition for the existence of a Hamiltonian cycle. (Most theorems are of this type!)

Some misunderstood the problem to mean that one has to prove that if d_x + d_z < n for any pair of nodes, then there is no Hamiltonian cycle exists in the graph. This can't be done, because it is not true. (Again, consider the above example.)

Some people attempted to give some sort of theoretical argument about why the statement should be false. Most or all of these attempts failed. The usual argument ran something like, "We try to obtain a proof by contradiction, [... attempt follows ...], but we failed to do so. Therefore the statement is false." This is simply invalid logic. Just because you failed a particular attempt to prove something does not mean the statement is false.

By far the simplest way to solve the problem is to exhibit a counterexample. Whenever you are asked to prove that some statement is false, this first thing you should do is to go looking for a counterexample. It is nice when you can find an entire family of counterexamples, as in the professor's solution sheet, but for this problem all you really need is one counterexample. The simplest here is the tree on three vertices.

Some people lost points by not providing a valid counterexample. That is, they gave a "counterexample" but it did not in fact satisfy the conditions of the statement. To be valid, it must be that for EVERY pair of vertices x and z in the example you have d_x + d_z >= n-1, not just for one pair of vertices. For example, a linear tree on 4 vertices is not a valid example since any pair of leaves fails to satisfy the required conditions.

Regarding problems 4 and 5

Most comments here fall under the general comments above.

Regarding problem 6

Many of the proofs (or a large part thereof) offered for problem 6 were copied nearly verbatim from Bonas's proof of the corresponding lemma in the text, but the adaptations were often nonsensical. For example, many of the proofs began, "Pick any vertex v in the tree. Assume v has degree d." Strictly speaking, this would imply that you are assuming that every vertex in the tree has degree d, which is patently false. It is much better to simply say something like, "Assume v is a vertex of degree d in the tree", which is probably what was really meant. So when you decide to mimic or adapt a proof from the text or another problem, do take care to read what you are writing, and that your adaptations actually make sense when you read them back. Also, do not skip the essential details. Some students who used the mimicking approach left out one or more of the essential details of Bonas's argument, which lost them points.

The "walks from a vertex of degree d" argument is perhaps the most intuitively appealing, and it was the approach most often employed, perhaps because it is the method used in Bonas's proof of the lemma. The other most common approach was to consider the forest obtained by removing a degree d vertex from a tree. However, this approach requires proving that the resulting graph is in fact a forest, and that it has at least d components. (In fact, it has exactly d components, but that takes more work to show.)

I was still a bit surprised that no one attempted the proof by means of total-degree argument, which is perhaps the shortest method, if somewhat less intuitive: Suppose T has n vertices, m leaves, and a vertex v with degree d > 1. Then besides the leaves and v, there are (n-m-1) vertices of degree 2 or more. Thus the total degree (sum of all vertex degrees) of T must be at least [m + d + 2(n-m-1)] = (2n+d-m-2). But the total degree is exactly twice the number edges, i.e. 2(n-1) =2n-2. Thus we have (2n+d-m-2) <= (2n-2), which implies d <= m. QED.