General comment #1

Many students are still struggling with terminology. Unfortunately, this sometimes makes their solution write-ups too ambiguous to score well. Specific examples are:

The difference between a partition of an integer versus a composition of an integer. In a composition of an integer, the order of the parts (summands) matters, while in a partition they do not (alternatively, we take the parts of the partition to always be in weakly decreasing order).

The difference between an Eulerian walk (or cycle) versus an ordinary walk (or cycle). An Eulerian walk contains EVERY edge of the graph.

The difference between a (connected) component of a graph and a subgraph. Every component of a graph is a subgraph, but not every subgraph of a graph is a component. Thus one can speak of THE component of a graph which contains a given vertex, and this component is always unique, but there is generally not any unique subgraph which contains the given vertex.

A bridge is a type of edge in a graph, but not all edges are bridges. (A bridge is an edge whose deletion increases the number of connected components in the resulting graph.)

For this course, a graph is defined to have no loops or multiple edges. When we allow multiple edges, our convention is to call it a multigraph. Some of the problems in this set, such as #3 and #6, are best solved using or assuming multigraphs. (Many of the theorems you are learning apply equally well to multigraphs as to graphs.) Many students did so in their solution, but I think no one made the explicit distinction. I did not deduct for this, but it is good form to use the proper terminology.

General comment #2

Many students lose points because they do not describe the "set-up" for their problem. For example, they will start off their solution by immediately talking about "the graph" or "the composition" or some other term which is not in the problem statement, without defining or describing what graph or composition, etc. they are talking about. This is an easy mistake to make when you already have a solution method in mind when you begin your write-up. But you must not assume that the object you have in mind will be obvious to the reader (me). Take the time to describe precisely how you are modeling the problem and what your terms are.

General comment #3

Sometimes a student will offer two proofs or solutions for a given problem. One of my past professors handled this situation this way: he would deduct points for errors in both solutions from the total available for the problem. So if you lost one point in one solution, and two points in the other, you were marked off a total of three points on the problem. I am adopting a more lenient policy. I will grade the first solution offered and will ignore the second. So give it your best shot on the first one.

Regarding problem #2

Almost all students argued by modeling the problem as a graph, though hardly anyone mentioned this step. I did not deduct for failing to mention it for this problem, since most of the students failed to do so and because the graph in question is fairly obvious. But it is better form to explicitly mention that one is doing this, and how the graph is constructed, i.e. what are the vertices, what are the edges, etc. This is especially important for some problems where the choice of graph is not obvious.

Regarding problem #3

This problem gave grief to many students, not to mention the grader. Most students seemed to have at least some notion of how to prove it, but many struggled to provide a clear, coherent argument. One symptom was poor command of terminology (see general comment #1 above). Most students followed the hint and attempted an inductive proof. However, some students, for the inductive step, began by positing some (presumably fixed) graph with 2k odd-degree vertices and then attempted to create a larger graph with 2k+2 odd-degree vertices by "adding two odd- degree vertices". Usually the construction was too vague to be well-defined. This approach is probably doomed from the start since one must show that the proposition holds for all graphs with 2k+2 odd-degree vertices, and it is unlikely that any fixed graph (with 2k odd-degree vertices) will universally be a subgraph of all graphs with 2k+2 odd-degree vertices. The problem is easiest to solve using multigraphs, and the proper leverage for the inductive step is to reduce to an earlier case (the I.H.), not by adding vertices, but rather by adding an edge between an arbitrary pair of odd-degree vertices, creating a new graph which falls into an earlier case. Some students did this step correctly, but failed to follow through, failing to show how a solution (graph tracing) in the new graph is used to provide a solution (tracing) in the original graph.

Regarding problems #4 and #5

Apparently many students misunderstood the problem statement, assuming that the problem was letting a_n be the number of compositions of n that have more than one part rather than the correct interpretation: the number of compositions of n in which each part is at least 2. Most students who made a mistake in problem #4 made the same mistake in problem #5.

Regarding problem #6

Most students solved this problem, though I felt I was rather lenient on this problem. One pattern I noticed was that many students argued along the lines of "Assume that 10 games have been played and that no one has played more than two games. Now add one more game ..." I generally gave credit for this, though really this is not a good way to argue the problem. In general, if you use the "scenario" approach to an argument, you have to handle other scenarios as well, either showing that they cannot happen, or that they reduce to your first one, etc. Sometimes it is the best way to argue a solution, but not in this problem. Here it is best to just go directly for either the inequalities implied by vertex-degree arguments or for the pigeonhole principle in some guise. I also noticed that some students made claims such as "Every player must play at least one (or two) games." or that "At least two players must have played at least three games." These are false. The problem statement says nothing about the tournament format, nor does it exclude the possibility of a player playing a given opponent more than once. So in one pathological case, player #1 has played 11 games: two each with players #2, #3, #4, #5, and #6, and one with player #7, while players #8, #9, and #10 have not played any games at all. I generally did not mark down for these claims as long as their final argument was correct and did not depend on the false claims.