# MATH 313 - Graph Theory Spring 2016

Professor: Erika L.C. King
Email: eking@hws.edu
Office: Lansing 304
Phone: (315) 781-3355

Office Hours: M: 1:30-3:30pm, W: 2:00-4:00pm, F: 10:30am-Noon, and by appointment
Class Schedule: held TTh 1:30-2:55pm in Lansing 301
Course Syllabus
Proof Writing and Presentation Tips
Possible Quiz Questions

### READING/EXAM WEEK: May 4 - May 10

IMPORTANT: Everyone will need to fill out a partner evaluation before the end of finals. That can be completed at any time during office hours, at the end of the review session or by appointment.

• Read Sections 10.1, 10.3 and 10.4. This includes history of the four color theorem, edge coloring, and the Heawood Map Coloring Theorem.
• Complete the following exercises: 10.13 (page 280), 10.17 and 10.19 (page 288).

Review Session: Friday, May 6th, 10:30am-Noon in Lansing 301

• Bring questions!
• Remember I will be looking for volunteers to present 10.5 (page 278), 6.17 (page 151), and 4.19 (pages 93-94). These will be a good review. If there is interest in more than three presentations, let me know and I could find a few more questions. Remember that the "solutions" at the back of the book are not usually complete, and that presentations should include definitions and some sort of visual diagram. If none of the people who haven't presented both required times claim the problem, those who have can get bonus points for doing extra presentations!

Office Hours:

• Wednesday, May 4: 1:30pm-3:30pm
• Thursday, May 5: 3:15pm-4:15pm
• Friday, May 6: 1:00pm-2:00pm
• Monday, May 9: 11:30am-1:30pm
• By appointment

Final Exam: Tuesday, May 10th 8:30am-11:30am in Lansing 301.

### WEEK 15: May 2-3

There will be no quiz this week! No more quizzes!

REMINDER: Your final paper for the article project is due MONDAY, May 2 by 4:00PM.

Reading and Practice Problems for class Tuesday, May 3:

• Read Section 10.2 (pages 267-277). (This is a reminder of the readings I asked you to start last week.)
• Complete the following exercises: 10.1, 10.5, 10.7, 10.9, 10.11 (pages 278-279). (This is a reminder of the problems I asked you to start last week.)
• Pet Showcase: Prepare to present your three favorite facts about your pets. One of these facts may be in relation to the new topics we learned from your presentations (list coloring, domination, star forests, etc.), but two should be from the topics we discussed in class at some point in the semester before the presentations. Each pet presentation need only be a few minutes. The idea is that by doing this we will review many of the topics we discussed throughout the semester with connections to specific graph families to reinforce them in our minds.
• I may also be looking for a volunteer to present 10.5 (page 278). We may not have time for this on Tuesday, but if not, this problem will be available for presentation at the review session.

LAST Collected Assignment (Due TUESDAY, MAY 3 by 4:00PM):

• Complete exercise 9.26 (page 248).
• Complete exercise 9.28 (page 248). For part (a), prove the result using Theorems and Corollaries and then ALSO draw an embedding of K_7 on the torus.
• Complete exercises 10.4, 10.6 and 10.12 (pages 278-280). Be sure to explain the graph model clearly for Exercise 10.12.
• You may also resubmit the Notebook problems that were due April 8, April 15 or April 22. Remember that you must turn in your earlier draft(s) with any resubmission.

BONUS Assignment (Due TUESDAY, MAY 3 by 4:00PM):

I will be looking for very precise and concise proofs. Treat this assignment the same as a Notebook Problem assignment. There should be no collaboration. You may complete any of the parts of this assignment to earn points. You do not have to turn in all four parts, though it would be great if everyone did! Any points earned on this assignment will contribute to your overall homework grade. Note that it is more important to do your Notebook rewrites than to do the bonus. Do not spend much time on the bonus until after you have worked through your rewrites!

A graph is $k$-critical if it has chromatic number $k$ and the deletion of any vertex yields a graph with a smaller chromatic number.

• (4 points) Find all 2-critical and 3-critical graphs. Explain why you have found them all.
• (2 points) Give an example of a 4-critical graph. Explain why your example works.
• (5 points) Prove that if G is $k$-critical, then every vertex of G has degree at least $k-1$.
• (5 points) Prove that if G is $k$-critical, then G has no cut-vertices.

Note that I will give you a free 24-hr extension for the assignments due this Tuesday. NO assignments will be accepted after 4:00 on Wednesday. This is a 24-hr extension, not a 24-hr and five minute extension!

### WEEK 14: April 25-29

There will be no quiz this week! Actually, there will be no more quizzes!

There will be no collected assignment due this Friday, but there will be a last collected assignment due the last day of classes.

Article Project: Presentations this week!!!

• See handout for details. I'm excited to see the fruits of your hard work!
• This is worth 50 points.
• Note that you should be taking notes and actively involved during the presentations in class, as you will be asked a question on the final exam that has to do with another group's presentation.

Reading and Practice Problems you should be working on:

• Read Section 10.2 (pages 267-277). Carefully work through Theorem 10.9 especially; this is the theorem we spoke briefly about in class, but for which we did not go into details. Be sure check out Examples 10.4 and 10.6 for applications of graph coloring to scheduling and traffic control.
• Complete the following exercises: 10.1, 10.5, 10.7, 10.9, 10.11 (pages 278-279).

Presentation and other fun in class Tuesday, April 26:

• Mei-Wah Choi and Hermione Yu on the article "On a List Coloring Conjecture of Reed."
• Remember to bring your laptops or other devices on which you can complete evaluations.
• Without reading ahead, think about how you might show that every planar graph is 5-colorable. We will show this!

Presentations in class Thursday, April 28:

• Mark Curiel and Chris Holoman on the article "Star forests, dominating sets and Ramsey-type problems."
• Jacque Kane and Matt McPartlon on the article "Dominating Sets in Planar Graphs."

Although there is no regular collected assignment due Friday, you are encouraged to resubmit the Notebook problems that were due April 1 (last chance for this one!), April 8, April 15 or April 22. Remember that you must turn in your first draft(s) with any resubmission.

### WEEK 13: April 18-22

Quiz 9 on Tuesday, April 19th covering Sections 6.1, 6.2 and 9.1. Note that this will be our LAST quiz. ;-)

Article Project: Rough Draft Assignment (Due Monday, April 18 by 4:00PM):

• Turn in a rough draft of your article project paper. See handout for details. Make sure you have fulfilled the requirements. The more like a final paper this is, the better.
• This is worth 10 points. Only one assignment is due per article team.

Reading and Practice Problems for class Tuesday, April 19:

• Read Joe Gallian's article "How to Give a Good Talk". It shouldn't take you long and it should give you some good thoughts to keep in mind as you prepare for next week.
• Read Section 9.1 (pages 227-238). Check out the slightly different approach to proving Theorem 9.2.
• Have fun completing the following exercises: 9.1, 9.3, 9.5, 9.7, 9.11, 9.13(c) and 9.15 (pages 238-240)! :-)

Reading and Practice Problems for class Thursday, April 21:

• Read Section 9.2 (pages 241-248). Be sure to check out the proof of Theorem 9.9 (pages 245-247) and see how the neat ideas we discussed in class fit into the proof by induction. There are also a bunch of nice diagrams to help understand all the concepts.
• Complete the following exercises: 9.17 and 9.19 (pages 240-241); 9.23, 9.25 and 9.27 (page 248).
• Here is an exercise based on 9.17 (page 240): (a) Show $\bar{C_n}$ is nonplanar for $n\geq 8$. (b) Show that $\bar{C_7}$ satisfies the inequality in Theorem 9.2 and yet the graph is nonplanar. I will be looking for a volunteer to present this version of 9.17.

Collected Assignment (Due Friday, April 22 by 3:00PM):

• Prove that if $G$ is a planar graph with at least 11 vertices, then $\bar{G}$ is nonplanar.
• Prove that there does not exist a connected plane graph that has seven regions and all vertices of degree four.
• Find a graph $G$ with degree sequence (4, 4, 4, 4, 3, 3) such that (a) $G$ is planar (b) $G$ is nonplanar.
• Complete exercises 9.2, 9.16 and 9.20 (pages 238-241). Note that some of these problems refer to maximal planar graphs. Check out page 233 in our textbook to review the definition and the consequences of the definition as we discussed in class.
• Notebook Problem: Complete exercise 9.14 (page 240). Part (e): Use Wagner's Theorem to show that the Petersen graph is nonplanar (you will have to take a gander at 9.3 pages 249-251 to do this part). Note the hypotheses at the beginning of the problem related to $G$ apply wherever $G$ is mentioned. Remember: (1) Turn in the notebook problems on a separate piece of paper from your other homework, and (2) notebook problems must be done on your own.
• You may also resubmit the Notebook problems that were due March 25 (last chance on this one), April 1, April 8, or April 15. Remember that you must turn in your earlier draft(s) with any resubmission.

### WEEK 12: April 11-15

I decided that I would give you a week off from quizzes! No quiz this week!

Article Project: Proof Rough Draft Assignment (Due Monday, April 11 by 4:00PM):

• Write up a proof of a theorem that you plan to include in your article project paper. See handout for details.
• This is worth 10 points. Only one assignment is due per article team.

Reading and Practice Problems for class Tuesday, April 12:

• Reread Section 6.1 (pages 133-139) and read Section 6.2 (pages 140-150).
• On page 148, the authors define the closure of a graph. Work through the examples and be prepared to demonstrate that you understand what closure means. What results are there that relate Hamiltonicity to closure?
• Complete the following exercises: 6.7 (page 140), 6.9 (page 150).

Reading and Practice Problems for class Thursday, April 14:

• Review the group worksheet from Tuesday's class. Bring any questions you have about our results to office hours or class. Without looking at the text, see if you can figure out a bound on the number of edges in terms of the number of vertices.
• Reread Section 6.2 (pages 140-150), paying special attention to pages 148-150 where closure and Pósa's Theorem are discussed.
• Complete the following exercises: 6.11, 6.15, 6.19 and 6.21 (pages 150-152).
• I will be looking for a volunteer to present 6.21 (page 152). Note that the back of the book gives a hint, but not a complete solution. The presentor should be ready to fill in the gaps of the given outline and remind the audience of important definitions.

Collected Assignment (Due Friday, April 15 by 3:00PM):

• Exercises 6.10, 6.12, 6.18 and 6.24 (pages 150-152).
• Complete this worksheet on Closure and Hamiltonicity.
• Notebook Problem: Exercise 6.16 (page 151). Remember: (1) Turn in the notebook problems on a separate piece of paper from your other homework, and (2) notebook problems must be done on your own.
• You may also resubmit the Notebook problems that were due March 25, April 1 or April 8. Remember that you must turn in your earlier draft(s) with any resubmission.

### WEEK 11: April 4-8

Quiz 8 on Tuesday, April 5th covering Sections 5.3-5.4.

Article Project: Outline Assignment (Due Monday, April 4 by 4:00PM):

• Make an outline of your article project paper. See handout for details.
• Discuss when you would be available to meet as a team. Meeting times will be Wednesday, April 6, Thursday April 7 or Friday, April 8. Make a list of times you are available (as a team) on those days.
• This is worth 10 points. Only one assignment is due per article team.

Reading and Practice Problems for class Tuesday, April 5:

• Reread Section 5.4 (pages 124-129). Review our proof of the edge-version of Menger's Theorem and compare it to the book's proof of Menger's Theorem.
• Continue working on the group worksheet from last Thursday's class about Eulerian and Hamiltonian graphs. Feel free to do this with other members of the class, but avoid looking at chapter six of your books! This is not actually a particularly long worksheet. You should try to finish it! Be ready to discuss results in class.
• Complete the following exercises: 6.1 and 6.2 (page 139). Try these withOUT looking at the section reading! Note that a graph is called Eulerian if it contains an Eulerian circuit.

Bonus Assignment (Due Tuesday, April 5 by 4:00PM):

• You can earn up to five points on your exam by completing any one of the following bonus questions. You may do more than one, but you can earn at most five points total, and you must earn at least three points on one of them before I will count points from a second one. Although you may consult me and use your text for these problems, you may NOT discuss them with anyone else nor use any other resources. Turn these in separately from your other homework. Since this is bonus, these proofs should be very high quality.
• Problem 7 from your exam using the First Theorem of Graph Theory.
• BONUS 1 from your midterm exam if you did not earn points for it already.
• BONUS 2 from your midterm exam.

Reading and Practice Problems for class Thursday, April 7:

• Read Section 6.1 (pages 133-139) and start reading Section 6.2. Theorem 6.1 is the theorem we started proving in class. Check out their proof by contradiction and think about how to finish our proof by induction.
• Read Section 6.4: Excursion: Early Books of Graph Theory (pages 156-159) and check out the graph theory poem on page 159.
• Complete the following exercises: 6.3, 6.5 and 6.8 (pages 139-140).
• I will be looking for a volunteer to present 6.3. Be sure to remind everyone of definitions and include an example.

Collected Assignment (Due Friday, April 8 by 3:00PM):

• Prove that there exists no 3-connected graph with exactly seven edges.
• Exercise 5.32 (page 124).
• Exercise 5.34 (page 129).
• Exercises 6.4 and 6.6 (pages 139-140).
• Notebook Problem: Exercise 5.36 (page 130). Remember: (1) Turn in the notebook problems on a separate piece of paper from your other homework, and (2) notebook problems must be done on your own.
• You may also resubmit the Notebook problems that were due March 4 (last chance for this one), March 25 or April 1. Remember that you must turn in your earlier draft(s) with any resubmission.

### WEEK 10: March 28 - April 1

Quiz 7 on Tuesday, April 2nd covering Sections 5.1-5.3.

Reading and Practice Problems for class Tuesday, March 29:

• Read the article project handout and make sure you have no questions about what is expected.
• Remember your pets! We talked about the connectivity and edge connectivity of your pets in Thursday's class. What else have you learned about them recently? Add any new information to your pet poster. How many blocks do your pet graphs have?
• Review your work on the handout from last week's classes. We discussed most of it, but go back and finish any parts you did not and be sure that the concepts make sense.
• Reread Section 5.3 (pages 115-121).
• Review the first part of the proof of Whitney's Theorem that we did in class. Then work on finishing the proof. On the back of the handout, we have two cases. I would like to have two volunteers, one to present each of the cases. After you work on trying to finish the proof on your own, review your reading of Section 5.3 and check the proof of Whitney's theorem there to see if you missed anything. Are you clear why we have to be so careful in choosing the vertex cut in Case 2?
• Complete the following exercises: 5.25, 5.27, 5.29 and 5.31 (pages 122-123).

Reading and Practice Problems for class Thursday, March 31:

• Remember to be working on your article project outline.
• Talk with your partner about which presentation spot you want. Rank the four spots in order of preference. The options are Tuesday, April 26th at 10:20, Tuesday, April 26th at (roughly) 11:05, Thursday, April 28th at 10:20, and Thursday, April 28th at (roughly) 11:05. We will finalize times on Thursday.
• Read Section 5.4 (pages 124-129). Work through the proof of Menger's Theorem. We will continue proving the edge-version of Menger's Theorem (Theorem 5.21) in class on Thursday.Explore the other theorems in this section. Can you guess which is also referred to as "The Fan Lemma"?
• After we finish proving the edge-version of Menger's Theorem in class, I will be looking for a volunteer to present 5.33. In addition to 5.33, the presenter should generalize the statement and explain how the generalized statement would be proven. Remember that a proof of this is in the book; you should of course try to solve it without the book first. The presentor is expected to give an overview, remind people of definitions, explain each step and be prepared to answer questions.
• Complete the following exercises: 5.33 and 5.35 (pages 129-130).

Collected Assignment (Due Friday, April 1 by 3:00PM -- no foolin'!):

• Exercises 5.20, 5.26 (Hint: You are allowed to use anything you have already proved...even elsewhere in this assignment.) (pages 122-123) and 5.28(a)-(e) (pages 122-123).
• Exercise 5.30 (page 123).
• Notebook Problem: Prove: If the $diam(G)\leq 2$, then $\lambda(G)=\delta(G)$. Remember: (1) Turn in the notebook problems on a separate piece of paper from your other homework, and (2) notebook problems must be done on your own.
• You may also resubmit the Notebook problems that were due February 26 (REALLY the last chance for this one!), March 4 (you may have until April 8 to resubmit this one...but try for two resubmissions!!!) or March 25. Remember that you must turn in your earlier draft(s) with any resubmission.

### WEEK 9: March 21 - March 25

Have a great spring break!!!

There will be no quiz this week!

Reading and Practice Problems for class Tuesday, March 22:

• Review our group work on blocks from class on Tuesday, March 8. Work on the rest of the worksheet, make some conjectures and be ready to share your findings with the class.
• AFTER you have spent some time working on the group worksheet, read Section 5.2 (pages 111-114). Make sure the proofs of the theorems and corollary make sense.
• I will be looking for volunteer to present Exercise 5.7 (page 111).
• Complete the following exercises: 5.9, 5.11 and 5.13 (page 114).

Article Project: Definition Assignment (Due Wednesday, March 23 at 4:00PM):

• Make a list of vocabulary words you will need for your article. Find definitions of each of these words (they may not be in your paper). Of greatest interest are new definitions, but you may want to include definitions of terms we have used in class. For different teams this list may be different lengths, but I imagine there to be roughly ten terms in your list. This is an important first step to understanding your topic, so be sure you include any terms you will need.
• For each term, use an example to explain your definition. For example, if your term is a property some graphs have, give an example of a graph with the property and then also an example of a graph without the property. If your term is a graph parameter, find the value of that parameter in at least one graph.
• This is worth 10 points. Only one assignment is due per article team. Your score will be based on how well you define your terms and provide examples, and on whether you have included all the important terms you need. Feel free to ask me questions about this.

Reading and Practice Problems for class Thursday, March 24:

• Review your work on connectivity in Tuesday's class. Continue working on the questions you did not get to within your group, and try to attempt all questions at least up to question 10. Bring questions to class and be ready to discuss.
• Read Section 5.3 (pages 115-121). Pay special attention to the authors' discussion of $k$-connected vs. connectivity and $k$-edge-connected vs. edge-connectivity (pages 115-117); they do a good job of explaining these relationships. Be sure to work through the proofs, especially for Theorem 5.10. Note the discussion of Harary graphs, which we first learned about on page 39.
• Complete the following exercises: 5.17, 5.19 and 5.21 (pages 121-122). The "answers" in the back of the text for these do not provide explanations. Make sure you can. (As usual, try to figure out a solution on your own or with a partner first before you check the back.)

Collected Assignment (Due Friday, March 25 by 3:00PM):

• Exercises 5.2 (page 110), 5.12 and 5.16 (Note this asks for an example of one graph with two properties. Be sure you explain why your graph has the required properties.) (pages 114-116).
• Find two non-isomorphic connected graphs with six vertices, six edges, and three blocks.
• Construct graphs with the following properties. If one of the graphs we used in class fulfills the requirements, you should find a new graph that also fulfills the requirements and not use the same graph. Justify why your graph works.
1. A graph that has equal vertex and edge connectivity such that this value is not equal to the minimum degree.
2. A graph whose edge connectivity equals its minimum degree such that this value is not equal to the vertex connectivity.
3. A graph that is not complete such that its connectivity, edge connectivity and minimum degree all equal four.
• Notebook Problems:
1. Exercise 5.6 (page 110).
2. How many non-isomorphic connected graphs are there with seven vertices, seven edges, and three blocks? Justify your answer. (Hint: think about partitions.)
Remember: (1) Turn in the notebook problems on a separate piece of paper from your other homework, and (2) notebook problems must be done on your own.
• You may also resubmit the Notebook problems that were due February 19 (last chance for this one...I am giving you an extra week since we had break!), February 26 (last chance for this one!) or March 4. Remember that you must turn in your earlier draft(s) with any resubmission.

### WEEK 8: March 7 - March 11

Due to our midterm exam, there will be no quiz and no collected homework assignment due this week! There will however be a short introductory assignment for the article project due Friday.

Our Midterm Exam will be on Thursday, March 10th in class. The exam will cover 1.1-1.4, 2.1-2.3, 3.1, 3.2, 4.1-4.3, and 5.1.

Reading and Practice Problems for class Tuesday, March 8:

• Nice class discussions and research into cut-vertices last Thursday! Keep up the good work!
• Read Section 4.4 (pages 100-104). Check out the Cayley Tree Formula, Theorem 4.15 on page 103. This is a well-known result. Although we won't spend time working through this section in class, you should know a bit about what it discusses.
• Keep working on the worksheet we did in groups on cut-vertices on Thursday. See if you can prove any of the theorems we generated. Then generate some more!
• After you have worked on the worksheet, read Section 5.1 (pages 107-110). Some of the proofs of theorems we came up with in class are in here. Do they make sense?
• Complete the following exercises: 5.1, 5.3, 5.5 and 5.7 (pages 110-111).
• I will be looking for volunteer(s) for Exercise 2.13 and/or the "another practice problem" from February 4 as part of our review for the exam at the end of class.

Article project choice list (Due Tuesday, March 8 by 4:00PM):

• Together with your project partner, make a list of at least three of your top choices of articles. If you are interested in an article not on the list I gave you, be sure to discuss it with me ahead of time, or submit a brief paragraph describing why you are interested in in the article, as well as the first two pages of the article.

Reading and Practice Problems for class Thursday, March 10:

• Individually, work on the questions from the review sheet. Come to office hours if you have any questions or make an appointment if you cannot make my hours.
• Catch up on your practice problems and review your notes, quizzes, homeworks and groupwork sheets. Lots of cool stuff here! Have fun reviewing for the exam...REALLY, I mean it! :-)

Article Project: Introductory Assignment (Due Friday, March 11 at 3:00PM):

This is just a short assignment, worth 10 points towards your project, to make sure you take the first steps towards working on this project and to begin to familiarize yourself with MathSciNet. Only one assignment is due per article team. On the paper you turn in, be sure to list your project article title, as well as which abstract/article is included as a response to which of the parts in question two.
1. Obtain your complete article. You may take the first pages of your article from the envelope outside my office. Those first pages should include from what journal it came. The articles are available online via MathSciNet (a database available through our library; note it may be difficult to access it from off-campus). Let me know if you have any questions or any difficulty finding the article. Make one copy/print out of your article for each person on your team and one for me and turn in my copy as part one of this assignment (you should keep your copies so that you can start reading!). There are a couple of articles on the list that you can not obtain from MathSciNet. If you discover that yours is one of them, come see me and I will help help you obtain your complete article.
2. Explore MathSciNet a little.
1. Find one other paper written by one of the authors of your paper and turn in a MathSciNet review/abstract of that other paper.
2. Find one other paper in the same area as your paper, but written by someone different than the authors of your paper, and turn in a MathSciNet review/abstract of that other paper.
3. Glancing through your article and the reference list at the end of it, choose another article that would be helpful for you to have in order to complete your project. It is possible that this is the same as your answer to part (a) or (b), however, for this one, I would like you to try to obtain the complete article not just a review or abstract. If we do not have access to that article, say so and order it through interlibrary loan. If you need help with this, let me know. I want to be sure you have as much information as possible at your disposal.
4. Are there any graph theorists or mathematicians in general or scientists with the same last name as anyone on your project team?
5. What are author citations? Explain in your own words.
6. What do you find when you look for author citations for my undergraduate advisor Ruth Haas? What information does this give you?

Although there is no regular collected assignment due Friday, you are always welcome to resubmit Notebook problems. Possible resubmissions for this week are the Notebook problems that were due February 12 (last chance for this one!), February 19, February 26 or March 4. Remember that you must turn in your first draft(s) with any resubmission.

### WEEK 7: February 29 - March 4

Quiz 6 will be on Tuesday, March 1 covering last week's material (Sections 4.2 and the material we discussed on Thursday's group work sheet).

Reading and Practice Problems for class Tuesday, March 1:

• Review your fifth quiz and my comments. Also review what we covered in class on Thursday. Bring any questions you have about the quiz or material before the group work sheet either to office hours or class.
• Continue to work on the group work sheet from Thursday's class and bring further ideas to share with your group and the class as a whole. Can you come up with precise algorithms as requested in question 4 withOUT reading section 4.3?
• Complete the following exercise: 4.22 (page 94), 4.25 (page 99).

Article project partner list (Due Wednesday, March 2 by 4:00PM):

Make a list of whom you would like to work with for the article project following these guidelines:
• Your list should include at least three options ranked.
• If there is any one in the class whose approach to the project you believe would be incompatible with yours, please make a note of that on your paper as well.

Reading and Practice Problems for class Thursday, March 3:

• Review the beginning of the proof that Kruskal's Algorithm gives us a minimum weight spanning tree we discussed in class. Then try to see if you can figure out how to finish it following what we outlined at the end of class on Tuesday. Then do the next item on this list!
• Read Section 4.3 (pages 94-99). Pay special attention to the proofs. Theorem 4.11 is the theorem we already started proving in class, but you should make sure you also believe that Prim's algorithm produces a minimum weight spanning tree as well (i.e. the proof of Theorem 4.12 on pages 98-99).
• Complete the following exercises: 4.27, 4.29 and 4.31 (pages 99-100).
• I will be looking for a volunteer(s) to present the proof of Theorem 4.11 and/or exercise 4.31 (page 100). Be sure you try 4.31 before you check the answer in the back of the book. Can you come up with a different solution? Remember that the back of the book usually does not give complete proofs/solutions.

Collected Assignment (Due Friday, March 4 by 3:00PM):

• Exercises 4.8, 4.20 (pages 92-94).
• Exercise: Label the edges of the wheel $W_7$ with the weights $1,1,2,2,3,3,\dots,6,6$ in such a way that the number of minimum weight spanning trees is (a) one, (b) more than one.
• Complete the exercise on this worksheet.
• Notebook Problems: Exercises 4.26 and 4.30 (pages 99-100). (Remember: (a) Turn these in on a separate piece of paper from your other homework, and (b) notebook problems must be done on your own.)
• You may also resubmit the Notebook problems that were due February 5 (last time for this one!), February 12, February 19 and February 26. Remember that you must turn in your earlier draft(s) with any resubmission. Also note that you may turn in resubmissions on any day of the week, you need not wait until a Friday.

### WEEK 6: February 22-26

Our sixth colloquium will be on Wednesday, February 24th, probably at 4:30. More information will be forthcoming.

Quiz 5 will be on Tuesday, February 23rd covering last week's material (Sections 3.1, 3.2, 4.1 and 4.2).

Reading and Practice Problems for class Tuesday, February 23:

• Review your fourth quiz and my comments. Also review what we covered in class on Thursday. Bring any remaining questions you have on either to office hours or class.
• I will be looking for a volunteer to present a nice version of the proof we sketched out in class on Thursday, showing that if every two vertices in $T$ are joined by a unique path, then $T$ is connected and has size $n-1$. The presentation should include all the details we discussed, but did not write down, pulled together in a coherent way. As usual the presentor is expected to give an overview, remind people of definitions, explain each step and be prepared to answer questions. We have had good presentations so far - I am looking forward to seeing more!
• Reread Section 4.1 and read Section 4.2 (pages 85-92). Be sure to read the paragraph after the proof of Theorem 4.3 on page 89 extra carefully, noting, the importance of leaves in induction proofs. Also be sure you are clear about the comments in the paragraph following the solution of Example 4.5 on page 90. This is a reiteration of a point the authors have made several times. Finally, proof by minimum counterexample is not a proof technique we tend to discuss in MATH 135, but it comes up in lots of mathematical areas and we like to use it in graph theory. The proof of Theorem 4.7 on page 91 is one example of an application of this technique. You may want to read a summary of this technique in Appendix 3.5 on page 395. We will also discuss this proof in class.
• Another presentation opportunity: The book has a proof showing that every tree has at least two leaves. There are at least two other proofs, one of which uses induction. Make sure you understand the book's proof (of Theorem 4.3), and find at least one other proof. I would like someone to present a summary of the book's proof and then show at least one alternate proof.
• Complete the following exercises: 4.7, 4.9, 4.13, 4.15 (pages 92-93).

Reading and Practice Problems for class Thursday, February 25:

• Review our proof on the handout for the Equivalent Properties to the Definition of a Tree, and carefully work through the last two parts which we did not discuss in class.
• Reread Section 4.2 (pages 87-92). Be sure to work carefully through the proof of Theorem 4.9, we will discuss this briefly in class. Isn't that neat!!!
• Complete the following exercises: 4.11, 4.17, 4.19, 4.21 and 4.23 (pages 93-94).
• I will be looking for a volunteer(s) to present exercise 4.17 (parts b and d) and/or exercise 4.23 (page 93). It would be great to see those of you who have not yet presented get up there, but everyone should be ready to present!

Collected Assignment (Due Friday, February 26 by 3:00PM):

• Exercises 4.4 and 4.6 (page 87), 4.12, 4.14 and 4.18 (page 93).
• Application: Come up with an application of Graph Theory to YOUR life. You all have another major or a minor besides mathematics. How could graph theory help solve a problem in your other area of interest? Your work should ask a question, then show how the question can be modeled with graph theory. Remember to do this you need to define what the vertices and edges represent as well as reword the question in graph theoretic terms. If you are having trouble thinking of a question related to your other academic interests, try thinking about your extracurricular interests.
• Notebook Problem: Exercise 4.24 (page 94). (This problem has two parts! The second part is figuring out how to generalize the first part and then proving it! Cool!) (Remember: (a) Turn these in on a separate piece of paper from your other homework, and (b) notebook problems must be done on your own.).
• You may also resubmit the Notebook problems that were due February 5, February 12 and February 19. Remember that you must turn in your earlier draft(s) with any resubmission. Also note that you may turn in resubmissions on any day of the week, you need not wait until a Friday.

### WEEK 5: February 15-19

Happy Valentine's Day!

We will have TWO more colloquia this week! They will be on Wednesday, February 17th and Friday, February 19th. I believe that both talks will be at 4:30, but more information will be forthcoming.

Quiz 4 will be on Tuesday, February 16th covering last week's material (Sections 2.1-2.4).

Reading and Practice Problems for class Tuesday, February 16:

• Review your third quiz and my comments. Also review what we covered in class on Thursday. Bring any remaining questions you have on either to office hours or class.
• Remember your pets! What have you learned about them recently? Add any new information to your pet poster and bring it to class on Tuesday to share.
• Read Sections 3.1 and 3.2 (pages 55-65), paying special attention to the proof of Theorem 3.6 on page 64.
• For even more fun, check out Sections 3.3 (pages 66-74). Those of you who already took MATH 375 might find this particularly interesting.
• Complete the following exercises: 2.39 (page 50), 3.3, 3.13 and 3.15 (pages 62-63), 3.17 and 3.19 (pages 65-66).
• I will be looking for a volunteer to present exercise 3.13 (page 63). Note that a proof of this is in the book; you should of course try to solve it without the book first. As usual the presentor is expected to give an overview, remind people of definitions, explain each step and be prepared to answer questions. We have had good presentations so far - I am looking forward to seeing more!

Reading and Practice Problems for class Thursday, February 18:

• I will be expecting a volunteer to present exercise 3.13 (page 63). Note that a proof of this is in the book, but you should of course try to solve it without the book first. As usual the presentor is expected to give an overview, remind people of definitions, explain each step and be prepared to answer questions. We have had some good presentations so far - I am looking forward to seeing more!
• Review Sections 3.1 and 3.2 and what we discussed about isomorphisms in class. Bring any lingering questions you have to class and/or office hours.
• Complete the following exercises: 4.1 and 4.5 (page 87).

Collected Assignment (Due Friday, February 19 by 3:00PM):

• Exercises 2.32 (a) and (e) and also a new (f) using following sequence: 6,6,6,6,4,3,3,0, applying Theorem 2.10 (also known as the Havel-Hakimi Theorem) at least three times for each part (page 47), 2.34 and 2.36 (also page 47), 3.10 (page 63, obviously you should justify your answer for this one!), 3.18 (page 65, and again you need to justify!) and 4.2 (page 87).
• Notebook Problems: (1) Prove the following statement: If diam$(G)\geq 3$, then diam$(\overline{G})\leq 3$. (2) Exercise 3.14 (note that 3.13 is a good example to review if you want to prove the statement and 3.15 if you want to disprove it) (page 63). Be sure to include all necessary details. (Remember: (a) Turn these in on a separate piece of paper from your other homework, and (b) notebook problems must be done on your own.).
• You may also resubmit the Notebook problems that were due February 5, and February 12. Remember that you must turn in your earlier draft(s) with any resubmission. Also note that you may turn in resubmissions on any day, you need not wait until a Friday.

### WEEK 4: February 8-12

Our second colloquium will be on Monday, February 8th. More information will be forthcoming. Note that there will also be colloquium on February 11th.

Quiz 3 will be on Tuesday, February 9th covering last week's material (Sections 2.1 and 2.2).

Reading and Practice Problems for class Tuesday, February 9:

• Review your second quiz and my comments. Also review what we covered in class on Thursday. Bring any remaining questions you have on either to office hours or class.
• I will be looking for a volunteer(s) to present 1.17, 2.7 or an additional practice problem (or all of the above). Please be prepared to present at least one of these to the class. You may speak with me ahead of time about these and you may bring your notes (though not your text) to the board.
• Don't forget your pets! What have you learned about them recently? Does the family of regular graphs intersect with your pet(s) at all? Add any new information to your pet poster.
• Read Section 2.2 (pages 38-41). Check out Harary graphs (page 39). Frank Harary was my academic grandfather...and quite a character! Also be sure to work through Theorem 2.7 and its proof (page 40) - neat stuff!!!
• Complete the following exercises: 2.1 (this is a good introduction to thinking about material in Section 2.3), 2.15, and 2.18 (pages 36-8), and 2.21 and 2.22 (page 42). Note that Exercise 2.22 helps illustrate Theorem 2.7. I will be looking for a volunteer for this one on Thursday!
• Start reading Section 2.3 (pages 43-47).

In order to meet with a candidate on Friday, the last half hour of my office hours will be shifted later. My hours will be 10:30-11:30am and 2:00-2:30pm.

Reading and Practice Problems for class Thursday, February 11:

• Reread Section 2.2 (pages 38-41) to make sure you are ready to do Exercise 2.22! I will be looking for a volunteer! (Note that I asked you to work on that for Tuesday!) Since the solution will use Theorem 2.7 in part of the answer, be sure you can remind the class what the statement of the theorem is.
• Read Section 2.3 (pages 43-47) and Section 2.4 (pages 48-49). Start reading Section 3.1. In particular, look closely at the proof of Theorem 2.10 on page 45. This is the proof that we were working on at the end of class on Tuesday. See if you can be ready to fill in the blanks at the beginning of class on Thursday.
• Complete the following exercises: 2.23, 2.24 (Note if you want to show a value $k$ is minimum, you must show both that $k$ is possible and that you cannot do better than $k$. In other words, you are trying to show that $k$ is sharp!), 2.27 and 2.29 (pages 42-43), 2.31 (note that this is another way we can play with the sequence to get another graphical sequence, but it is still not random), 2.33 and 2.35 (page 47).
• I will be looking for a volunteer for Exercise 2.22 on page 42. Since you use Theorem 2.7 in part of your answer, be sure you can remind the class what the statement of the theorem is.

Collected Assignment (Due Friday, February 12 by 3:00PM):

• Exercise 2.2 on page 36 in our text. Be sure to explain your examples.
• Using graph theory, prove that in a gathering of six people there are either three mutual acquaintances or three mutual strangers. (This is actually a version of a Putnam exam problem from way before you were born. You have the tools to answer it. Think about defining a graph model and using complements. Some of you have looked at this question before, but did not have the precise terminology you have now; use your new definitions and rigorous proofs.)
• Exercises 2.6 and 2.14 on pages 37-38 in our text.
• Notebook Problem: Exercise 2.12 on page 37 in our text. (Remember: (1) Turn these in on a separate piece of paper from your other homework, and (2) notebook problems must be done on your own.).
• You may also resubmit the Notebook problems that were due February 5. Remember that you must turn in your first draft with any resubmission.

### WEEK 3: February 1-5

Our first colloquium will be on Friday, February 5th. More information will be forthcoming. Note that there will also be colloquia on February 8th and February 11th.

Quiz 2 will be on Tuesday, February 2nd covering last week's material (Sections 1.2-1.3).

Reading and Practice Problems for class Tuesday, February 2:

• Review your first quiz and my comments. Bring any remaining questions you have on it to office hours or class.
• Review the proof Matt did and the one that we started in class on Tuesday and make sure they make sense. Can you finish the bipartite proof without looking at the text? Reread Sections 1.3 and 1.4 (pages 19-28) in our text. Make sure you understand what k-partite graphs, multigraphs and digraphs are. We will not work with these too much, but you should know their definitions. Check to see if you have any additions for your pet graph poster.
• Hopefully I will have a chance to ask for a volunteer to present exercise 1.17 (page 18) on Tuesday. Please be prepared to present it to the class. I hope to have many volunteers!
• Complete the following exercises: 1.23, 1.29 and 1.33 (pages 25, 28-29 and 29 respectively).

The end of my office hours on Wednesday will be shifted. My hours will be 2:00-3:30pm and 4:00-4:30pm.

Reading and Practice Problems for class Thursday, February 4:

• Read my comments on your collected homework and notebook problems. Make sure they all make sense. Bring any questions to me and start reworking the notebook problem.
• Work on the degrees handout from class. We will break into groups to review your results and discuss questions and ideas, before whole class discussion. This should not be time for looking at the questions for the first time, however. I will ask groups and/or individuals to present parts of the solutions early on. Induction anyone? You are encouraged to meet with your group or other classmates to discuss!
• Read Section 2.1 (pages 31-36). Note the discussion of sharpness on page 35.
• Complete the following exercises: 2.3, 2.5, 2.7 and 2.13 (pages 36-37).
• Another practice problem: Suppose that a graph contains eight vertices and 21 edges. Explain how you know that this graph must contain at least one vertex that has degree less than or equal to five and at least one vertex that has degree greater than or equal to six.
• I will be looking for a volunteer(s) to present 1.17, 2.7 or an additional practice problem (or all of the above). Please be prepared to present it to the class. You may speak with me ahead of time about these and you may bring your notes (though not your text) to the board.

Collected Assignment (Due Friday, February 5 by 3:00PM):

• Exercises 1.24 and 1.26 (be sure to explain your answer) on pages 25-26 in our text.
• Prove or disprove the following statements. Assume u and v are vertices in an arbitrary graph G. (Note that "distinct" does not necessarily mean "disjoint".)
• The union of the edge sets of two distinct u,v-walks must contain a cycle.
• The union of the edge sets of two distinct u,v-paths must contain a cycle.
• Prove that every graph with n vertices and k edges has at least n-k components.
• Notebook Problems: A graph is called self-complementary if the graph and its complement are the same graph (we will learn that this means they are isomorphic).
1. Prove that if a graph is self-complementary, then it has 4k or 4k+1 vertices, where k is an integer.
2. Without using the theorem you proved for part one, find all self-complementary graphs on 6 vertices. Explain your work. There are at least two ways to prove this withOUT the above theorem. Can you derive both of them?
• (Remember: (1) Turn these in on a separate piece of paper from your other homework, and (2) notebook problems must be done on your own.).
• You may also resubmit the Notebook problem that was due Friday, January 29. Remember that you must turn in your first draft with any resubmission. Also remember that if you wish to resubmit this problem you must do so no later than Monday, February 9th at 4:00pm! This is an exception to the usual policy because I would like to give you a sample proof sooner rather than later.

### WEEK 2: January 25-29

Note that due to introductory appointments with you and my 135 students, some of my open office hours are shortened this week. The open hours for Monday are: 1:30-2:30. If you cannot make these times and need to see me, please make an appointment.

Quiz 1 will be on Tuesday, January 26th covering last week's material (Sections 1.1-1.2).

Reading and Practice Problems for class Tuesday, January 26:

• Finish and review the Walks-Trails-Paths worksheet from class and make sure that the concepts make sense. Jot down any questions you have and bring them to office hours and/or class.
• Reread Section 1.2 (pages 9-17) in your text, focusing especially on the proofs.
• Read Section 1.3 (pages 19-25) in your text. Remember to keep track of vocabulary and jot down partial or example graphs to help you understand the concepts. Ask yourself the kinds of questions I included on the reading guide for section 1.2.
• Complete the following exercises: 1.13 and 1.17 (pages 17-18) from your textbook. Also pay special attention to the proof of Theorem 1.11. Bring questions you have about these; we may start doing student presentations with one of these (including the proof of Theorem 1.11 - be sure to be able to illustrate your proof)! Also do exercise 1.21 on page 25.

Reading and Practice Problems for class Thursday, January 28:

• Review the proofs of theorems in Section 1.2 (pages 9-17) in your text. Pay special attention to the Theorems we did not discuss in class (1.7-1.9), especially Theorem 1.7 with equivalence relations (remember those?!). Reread Section 1.3 (pages 19-25) to be sure you understand the different classes of graphs. Read Section 1.4 (pages 26-28).
• Work on a poster for your pet graphs. Draw at least four of your graphs at the top of the page (unless your family is smaller than that). Investigate the questions we were posing in class and list any answers you find beneath your diagrams. Think of other questions you could ask.
• I will be looking for a volunteers to present exercise 1.17 (page 18) and a proof of Theorem 1.11. These were due Tuesday. Please be prepared to present at least one of them to the class.
• Complete the following exercises: 1.22, 1.25 (Note that you should be asking yourself why this theorem has the hypothesis that the graph has order at least 5 - do you see why?) and 1.27 (pages 25-26).

Collected Assignment (Due Friday, January 29 by 3:00PM):

• Exercises 1.15 (In addition to answering the stated question, respond to the following: does your explanation work for graphs of other orders?), 1.19 (be sure to explain your answer), and 1.20(a) (hint: your answer shouldn't be just a number) on pages 18-19 in our text.
• Find a graph with five vertices and exactly (a) one cycle, (b) three cycles, and (c) six cycles. Explain briefly.
• Notebook Problem: Exercise 1.16 on page 18 in our text (Remember: (1) Turn these in on a separate piece of paper from and not stapled to your other homework, and (2) notebook problems must be done on your own.).

### WEEK 1: January 19-22

Welcome to Graph Theory!!!

Collected Homework (Due Wednesday, January 20 at 4:00pm):

• Write an autobiographical essay as assigned on the syllabus.

Reading and Practice Problems for class Thursday, January 21:

• Read the syllabus again. In fact, read it two more times. Although we spent some time on this in class, we did not discuss every detail. You should be sure you have read all of it and are clear on all the policies and expectations. Please ask if you have questions. Note the paper copy I gave you is green so that you can easily find it.
• Familarize yourself with this website. Note that there is a link at the top of the page to our syllabus, should you lose the green one I handed out in class. The syllabus has a lot of vital information on it and you will likely want to refer back to it regularly. Also at the top of the page is a link to my grade scale. This will let you know what percentage you need to earn in order to obtain specific grades. In addition, there is a website I developed, Proof Writing and Presentation Tips, for my First Steps into Advanced Mathematics classes. It would be valuable for you to use this as a reference when you are preparing your homework and presentations for class.
• There are also two additional links at the top of the page. The first is a proposed weekly schedule of how you might organize your graph theory time outside of class. I wrote it Friday to Friday to be in line with when you receive your new collected assignments. Hopefully this will be useful to you in setting up your own schedule. The second is a link to a list of possible quiz questions to help you know what to expect on quizzes.
• Complete the group-work sheet from class. Bring any questions you have on this to class.
• Read Section 1.1 (pages 1-7) and Section 1.2 (pages 9-17) in your text. Remember to have a pencil in hand! For a guide to what to think about as you read a mathematical text in general, and these sections in particular, check out the first side of this handout. The second side of the handout has a definitions worksheet for you to fill out for class. I will not have these guides for all your reading assignments, but I hope that these will give you ideas about how to have a productive reading experience for the whole semester!
• Complete the following practice problems: 1.3 (page 7), 1.6 (page 7), 1.7 (pages 7-8), and 1.11 (page 17). Note that most odd problems have answers or hints in the back of the text. Be sure to try the problems first before looking there!

Collected Assignment (Due Friday, January 22 by 3:00PM):

• Exercise 1.10 on page 9 of our text. As part two of this exercise, come up with a question we might ask given this situation, and then describe what we would be looking for in the graphical representation.
• Draw all distinct graphs on four vertices. (This is number 4 from the group-work sheet from class. Hint: There are more than eight and less than 15 such graphs.)
• Exercise 1.12 on page 17 of our text. Describe carefully in graph theoretic terms why each example satisfies the requirements or why you can find no such example.

Hobart and William Smith Colleges: Department of Mathematics and Computer Science
Erika L.C. King