Math 381: Graph Theory Homework Assignments

General Advice on Homework

• Besides finding the anwer, always try to explain, as well as you can, how you know you have the correct answer.
• When solving problems, a systematic solution is better than guesswork. You often may find a solution by intelligent guessing, but then you should look for a way of showing that your solution is correct. This part needs to be systematic if it is to be completely convincing. (This will be clearer after a few days of class!)
• Allow 15 minutes per problem (minimum) before you give up, even if you feel you're getting nowhere. These problems need time for thought. If you're still stuck, go on to another problem. Return to the sticky problem later (say, the next day). Often, it then looks easier because you tried hard the first time and then gave your mind time to grind it up-I mean, to come up with ideas. To get the advantage of this method, you have to start the problems well ahead of time. Last-minute effort will not work well in this class.
• It's fine to work with other people, indeed I encourage it. However, you should write up your solutions yourself. Here's what you should do:
  1. Look at the problem first and think about it for at least a few minutes (preferably more--much more!).
  2. Discuss it with other people.
  3. Write up a solution in your own words. Don't copy from the notes of your discussion.
  I will not accept duplicated work. Anyway, it doesn't do you much good to copy or duplicate someone else's work. The purpose of graded homework is to tell you how well you're doing and how you can improve. That won't happen unless you follow these rules.
• If you have any question about the homework grading, you should see me promptly. Maybe you need me to explain something. Or maybe I made a mistake.

Rules for Hand-In Homework.

1. I expect complete written solutions that give full justification of the correctness of your answer. Answers without any justification will not be accepted. You'll gradually learn better what this means, so don't worry now, just do your best to explain your work.
2. Hand in a final draft: neat work that is well organized and not cramped. Use as much space as you need. Please also leave some extra space between problems for my comments.
3. You may discuss hand-in HW with other people, but you must write it up in your own words.
4. No little stubbies from tearing a page out of your binder. Remove them neatly, please!
5. Fasten the pages securely. Staples are best. Paper clips and folding a corner don't hold well; don't use them.

Sect. 10: ## 2(ii)(second graph) (and also go backwards: from the tree to the sequence, as a check), 5; Sect. 12 ## 5(ii), 10(Petersen graph); # C2.

---

Problem Set C

The problems refer to the graph H shown. (This is the same H as on the last test.)



1. Hamiltonicity:
   1. Show that H has a unique Hamiltonian cycle.
   2. Find all edges e such that H-e has no Hamiltonian cycle.
   
   
2. Planarity:
   1. Decide whether H is planar.
   2. Let H' be H with the edges x₆x₇ and x₁₀x₁₂ added. Decide whether H' is planar. Use two different methods if you can find the time.

---

HOMEWORK IX

For Wed. 4/3: