Some comments from Jose

  • When you give an answer you should make sure that you are covering two parts: showing that all the elements listed in your answer satisfy the property and checking that the elements that are not in you answer do not satisfy it. In problem 1 many of you forgot to say why if n>2 is even then K_n has no Eulerian trail.
  • Remember to ALWAYS check the hypothesis of a theorem before applying it. In problem #2 many students tried to apply Cor. 9.3 using that two vertices have degrees equal to 99 and the rest of vertices have degrees equal to 100. This is unfortunately a WRONG thing to do: to be able to apply Cor. 9.3 you need to know that the graph is connected beforehand. Having an Eulerian trail is a much stronger property than being connected and is usually harder to prove. For those who still do not believe that this argument is not correct here is a counterexample. Consider two disjoint copies of K_{101} and remove one edge. All the vertices in the resulting graph have degree 100 except for two vertices that have degree 99. However this graph is not connected so the Eulerian trail does not exist. (There is, however, a way to solve problem #2 using Eulerian trails. Indeed, the hypothesis of the problem implies that the *original* graph has a closed Eulerian trail. This is because all vertices of the original graph have even degrees and the graph is connected. We can go along this closed Eulerian trail in two directions, so there is a path from A to B that does not contain the edge AB. This gives the connectivity of the graph obtained from G be removing AB.)
  • I would suggest you do the exercise of reading aloud your homework, or even better, ask someone to read it aloud to you. That will help you notice where are you being clear and where you are not.
  • One more advise: When you finish writing a solution, read the problem again, go over ALL the hypothesis and check if and where you've used them. If you look at problem #2 and the flawed solution using 9.3, the main problem is that you are NOT using the connectivity of the original graph in any way.