Various comments on midterm #2 (Math 5707 Spring 2017):

- Exercise 1 was meant to be solved using Hall's Marriage Theorem, and this is how most of you did it. I think I have an alternative solution without Hall's Marriage Theorem, but it is long and painful and I have not thoroughly checked it.

- Exercise 2, on the other hand, was meant to be solved using a spanning tree, as I do in my suggested solutions ( http://www.cip.ifi.lmu.de/~grinberg/t/17s/mt2.pdf ). Note that there is a minor pitfall (namely, you need to put an edge "on reserve" -- the edge $e$ in my solution -- before constructing the spanning tree, since the spanning tree only has $|V|-1$ edges). However, some of you found rather nice proofs using Hall's Marriage Theorem.

- Exercise 1 and Exercise 2: When defining a bipartite graph of the form $(H; V, E)$, you need to make sure (e.g., by renaming vertices) that the sets $V$ and $E$ are disjoint. (But this is a trivial issue, and I have not taken off points for it; just saying.)

- Exercise 1 and Exercise 2: I still have seen some examples of incorrect inductions in your solutions. In the step from $n-1$ to $n$, you CANNOT simply assume that each $n$-vertex graph $G$ with $|E(G)| \geq |V(G)|$ can be obtained from an $n-1$-vertex graph with the same property by adding an extra vertex and some edges. In fact, try getting the $3$-cycle $C_3$ from a $2$-vertex graph in this way! When you remove a vertex from a graph, you should be prepared to lose various nice properties; sometimes you can gain them back in some way or keep them by removing the "right" vertex (i.e., a leaf when your graph is a tree), but there is no blanket guarantee that you always do.

- Exercise 3 has a short solution using Menger's theorem (the First Solution in my suggested solutions) and a loooong solution using the Stable Marriage Theorem (the Second Solution there). Beautiful as the second solution is, I really don't know how to make it slick; most of you who found it were missing various parts or just skipping verifications.

- Exercise 4 has turned out to be harder than I meant it to be, and in hindsight I see why: It is more a problem in enumerative combinatorics than a problem in graph theory. There is an solution using the "principle of inclusion and exclusion", and a similar solution that uses just basic properties of sums and truth values; but neither solution is very straightforward to come up with if you are new to the subject (and I guess the only experience with the subject we had in class was the proof of the Heinrich-Tittmann formula, which might have gone too fast). Some of you also found a third solution, using the "deletion-contraction" formula.

- Exercise 5: I gave 3 points for (a), 4 for (b), and 3 for (c). Yes, part (c) is a particular case of part (b), since $P_3$ is a tree.

- Exercise 5: Let me stress that a polynomial is NOT a function. It is a sequence of coefficients. The $x$ in $\chi_G(x)$ is an "indeterminate", not an integer, and thus there is no such thing as "coloring a graph with $x$ colors". This is why I use two different letters $x$ and $k$: The former stands for the indeterminate, while the latter stands for an actual nonnegative integer that tells you how many colors you have. Fortunately, a polynomial with (e.g.) real coefficients is uniquely determined by its values at the nonnegative integers; thus, if you can prove (in Exercise 5 (b)) that $\chi_T(k) = k (k-1)^{n-1}$ for all nonnegative integers $k$, then you automatically get the equality $\chi_T(x) = x (x-1)^{n-1}$ of polynomials. But $\chi_T(k)$ is still not the same as $\chi_T(x)$. If this sounds too academic to you, ask yourself why $\chi_T(1/2) = (1/2) (1/2 - 1)^{n-1}$ for an $n$-vertex tree $T$. This follows from the equality $\chi_T(x) = x (x-1)^{n-1}$ (because you can substitute $1/2$ for the indeterminate $x$), but this does not immediately follow from any reasoning about colorings (because what the heck is a $1/2$-coloring?). I have not taken off any points for getting these details wrong (unfortunately, they are often short-changed in undergraduate classes), but you need to be aware of them.

- Exercise 5: In part (a), some of you have argued that the polynomial $\chi_{K_n}$ has degree $n$ (by definition) and vanishes at $0, 1, ..., n-1$ (since $K_n$ has no $i$-colorings for $i < n$), and therefore must be $x (x-1) ... (x-n+1)$. This is almost correct: The argument shows that it is $p x (x-1) ... (x-n+1)$ for some constant $p$. You need to argue that this constant $p$ is $1$. One way to argue this is by observing that the leading term is $x^n$ (since the only $F \subseteq E$ for which the graph $(V, F)$ has $n$ connected components is the empty set).

- Exercise 6: On the course website, you can find three different solutions to this exercise (one by Sasha Pevzner, one by Nicholas Rancourt, and one by me). I personally like Sasha's one the most. The statement of the exercise is fairly well-known (and is related to the four-point condition for phylogenetic trees, although it is not precisely that condition), but unfortunately most proofs found on the internet (and even in books) are incomplete (to say the least). You cannot just draw a picture and claim that "the paths between the four points $x, y, z, w$ look like this"; you need to rigorously explain what "looking like this" means, and you need to prove it (which is usually rather painful).

- Exercise 7: I think the solution I give in my suggested solutions is the slickest one. (I also show some consequences of the exercise, which should explain where it comes from.)