# MATH 313 - Graph Theory Spring 2019

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

Office Hours: M 1:30-2:30pm, W 1:30-3:00pm, Th 3:30-4:30pm, F 9:30-11:00am, and by appointment
Class Schedule: held TTh 10:20-11:45am in Stern 117

### READING/EXAM WEEK: May 7 - May 13

IMPORTANT: Everyone will need to fill out a partner evaluation before the end of finals. You can do this after you finish your final exam on Saturday. Do NOT leave before you have done so!

Lost your final review sheet? Here is a copy.

Review Session: Wednesday, May 8th, 10:30am-Noon in Eaton 111

• Bring questions!
• If you are interested in presenting, let me know by Tuesday at noon. 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.

Office Hours:

Note that I have changed my Friday office hour to begin a half hour later than what I put on the review sheet I gave you (it is revised in the version posted above).
• Tuesday, May 7: 1:30pm--3:30pm
• Wednesday, May 8: 2:00pm--3:30pm
• Thursday, May 9: 3:00pm--4:30pm
• Friday, May 10: Noon--2:00pm
• By appointment

Final Exam: Saturday, May 11th 8:30am-11:30am in Demarest 117A.

### WEEK 15: May 6

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

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

### WEEK 14: April 29 - May 3

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

Presentation, reading, practice problems and other fun for class Tuesday, April 30:

• Ally, Haixin and Drew will present on Total Equitable List Coloring.
• Remember to bring your laptops or other devices on which you can complete evaluations.
• Reread Section 9.2 and review what we discussed in class!
• Think about the Greedy Coloring Algorithm, test it on a graph or two, then read Section 10.2 (pages 267-277). 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 (page 278).
• On Thursday, May 2nd, we will have a Pet Showcase! Start thinking about how you will share with your classmates all you have learned about your pets! A poster or another presentation medium should be part of your presentation. You have been collecting this information throughout the semester; now is the time to put it all together!

Article Project Final Exam Questions and Study Guide Assignment (Due Wednesday, May 1 by 4:00PM):

• See handout for details. This document should be a page or two in length.
• This is worth 10 points.

Reading and Practice Problems for class Thursday, May 2:

• Reread Section 10.2 (pages 267-277). Carefully work through Theorem 10.9 especially; this gives another upper bound for the chromatic number of a graph. Is it better? How easy is this to find? Remember to be sure check out Examples 10.4 and 10.6 for applications of graph coloring to scheduling and traffic control.
• The text gives the proof of Theorem 10.7 using the Greedy Algorithm. I also mentioned that this theorem could be proved by induction. Write out a sketch of what this proof would look like before class on Thursday. We will use this idea in other coloring proofs as well!
• Complete the following exercises: 10.9, 10.11 (page 279).
• 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, cops and robbers, pebbling, well-covered, 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. Your poster probably will have many more facts on it than you share. 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 Thursday, but if not, this problem will be available for presentation at the review session next Wednesday (more information on this will be forth coming on Thursday!). If we have time, first priority goes to those who have not yet presented. If there is more than one person interested in presenting who has not, we will roll a die for random selection for who presents. If nobody who has not presented is prepared, then we will invite second presentations, and so on.
• FREE EXTENSION: You may have until Tuesday, May 7th at 11:00am to turn in your last collected assignment and notebook resubmissions without penalty and without using a "FREE LATE"!

LAST Collected Assignment (Due Friday, May 3 by 3:00PM):

• FREE EXTENSION: You may have until Tuesday, May 7th at 11:00am to turn in this assignment without penalty and without using a "FREE LATE"!
• 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.
• Note that there is no new Notebook Problem due this week!
• You may also resubmit the Notebook problems that were due April 5 (Last Chance for this one!), April 12 (Final Chance: May 6), and April 26 (Final Chance: May 6). 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. Review our Notebook Problem Set Policy and be sure that you do at least one resubmission for each Notebook problem!

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

### WEEK 13: April 22 - April 26

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

Article Project: Presentations this week and next!!!

• See handout for details. I'm excited to see the fruits of your hard work!
• Remember to practice the presentation ahead of time and let me know if you want to meet to ask questions. You are welcome to ask questions about your presentation in office hours. While it is ideal for you to all be there when questions are asked, it is not required and it is fine if only one or two members of your team can be there.
• 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:

• Reread Section 9.2 and review what we discussed in class!
• Think about the Greedy Coloring Algorithm, test it on a graph or two, then read Section 10.2 (pages 267-277). 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 (page 278).
• On our last day of class, May 2nd, we will have a Pet Showcase! Start thinking about how you will share with your classmates all you have learned about your pets! A poster or another presentation medium should be part of your presentation. You have been collecting this information throughout the semester; now is the time to put it all together!

Presentations in class Tuesday, April 23:

• Everyone should be ON TIME to class!!! This should always be true, so if you have had issues with this, now is the time to make it right! There will be a five minute break in between presentations to allow the second group to set up. Please respect your classmates and participate while they are presenting (which includes any question and answer period).
• Andrew, Nick and AJ on Graph Pebbling
• Juliana, Taylor and Joon on A Game of Cops and Robbers

Presentations in class Thursday, April 25:

• Everyone should be ON TIME to class!!! This should always be true, so if you have had issues with this, now is the time to make it right! There will be a five minute break in between presentations to allow the second group to set up. Please respect your classmates and participate while they are presenting (which includes any question and answer period).
• Hadley, Sam and Peter on Well-Covered Cartesian Products
• Xiaohan, Kairuo and Genming on Domination Games

Collected Assignment (Due Friday, April 26 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.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 29 (Last Chance for this one!), April 5 (Final Chance: May 3), and April 12 (Final Chance: May 6). 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. Review our Notebook Problem Set Policy and be sure that you do at least one resubmission for each Notebook problem!

### WEEK 12: April 15 - April 19

Quiz 9, the LAST!, on Tuesday, April 16th covering last week's material (Sections 6.2 and pages 227-231 of Section 9.1).

Article Project: Rough Draft Assignment (Due Monday, April 15 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 16:

• Review our group work from class. Fill in any details you did not complete in class. Write down any questions you have.
• Read Section 9.1 (pages 227-238).
• 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)! :-)
• I will be looking for a volunteer to present 9.2. Be sure to use appropriate terminology and refer to appropriate theorems.

Reading and Practice Problems for class Thursday, April 18:

• 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.
• Reread Section 9.1 (pages 227-238). Check out the slightly different approach to proving Theorem 9.2. Explore Example 9.8 for an application of Kuratowski's Theorem.
• Read Section 9.2 (pages 241-248). Be sure to check out the 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 19 by 3:00PM):

• The next assignment (see below) is not due until Friday, April 26th! Depending on when your presentation is, you may wish to work on this sooner or later. Whatever you do, don't leave it until the last hour! You may turn it in whenever you have it complete before the due date!
• You may also resubmit the Notebook problems that were due March 29 (Final Chance: April 26), April 5 (Final Chance: May 3), and April 12 (Final Chance: May 6). 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. Review our Notebook Problem Set Policy and be sure that you do at least one resubmission for each Notebook problem!

Looking Ahead: Collected Assignment (Due Friday, April 26 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.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 29 (Last Chance for this one!), April 5 (Final Chance: May 3), and April 12 (Final Chance: May 6). 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. Review our Notebook Problem Set Policy and be sure that you do at least one resubmission for each Notebook problem!

### WEEK 11: April 8 - April 12

Quiz 8 on Tuesday, April 9th covering Sections 6.1-6.2.

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

• Make a conjecture and explain why you think it is a reasonable one. See handout for details.
• 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 9:

• Reread Section 6.2 (pages 140-150).
• I will be looking for a volunteer to present 6.3. Be sure to remind everyone of definitions and include an example.
• 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).
• Read Section 6.4: Excursion: Early Books of Graph Theory (pages 156-159) and check out the graph theory poem on page 159.

Reading and Practice Problems for class Thursday, April 11:

• Review proofs and theorems from Tuesday's class and bring any questions you have to office hours or class.
• 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 12 by 3:00PM):

• Exercises 6.4, 6.6 (pages 139-140) and 6.10 (page 150).
• 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 29 (Final Chance: April 26) and April 5 (Final Chance: May 3). 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. Review our Notebook Problem Set Policy and be sure that you do at least one resubmission for each Notebook problem!

### WEEK 10: April 1 - April 5

Quiz 7 will be on Tuesday, April 2 covering last week's material (Sections 5.3 and 5.4).

Reading and Practice Problems for class Tuesday, April 2:

• 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.
• One more chance: 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.
• Remember your pets! We talked about the connectivity of your pets. What else have you learned about them recently? What is their edge connectivity? Add any new information to your pet poster. How many blocks do your pet graphs have?
• Read Section 6.1 (pages 133-139). Remember to write down all vocabulary, take notes 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.
• Read Section 6.4: Excursion: Early Books of Graph Theory (pages 156-159) and check out the graph theory poem on page 159.

Optional BONUS Assignment (Due Tuesday, April 2 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, you may NOT use the internet nor any other resources. Turn these in separately from your other homework. Since this is bonus, these proofs must be very high quality in order to earn points.
• Problem 4.30 on page 100 of your text.
• BONUS 2 from your midterm exam. (Note: you may assume $G$ is connected.)

Article Project: Outline Assignment (Due Wednesday, April 3 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 Friday, April 5, Monday, April 8 or Tuesday, April 9. 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.

Sign up to present the Notebook problem due March 29th as soon as possible. See your email for details. Some of these meetings will be during regular office hours. After sign ups have occurred, I will let you know of any restrictions to open office hours.

Due to an appointment on Friday morning, my Friday office hours will be moved from the morning to the afternoon for this week. My hours will be Friday, April 5th, 1:30pm-2:30pm.

Reading and Practice Problems for class Thursday, April 4:

• 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! Collect properties that you think are necessary, sufficient or both for a graph to be Hamiltonian.
• Reread Section 6.1 (pages 133-139). Theorem 6.1 is the theorem about Eulerian graphs and even degree. Check out their proof by contradiction and think about how we might prove it by induction! (We will do this in class.)
• Go back and prove Exercise 4.8. How might this be useful in the proof of Theorem 6.1?
• Read pages 140-145 of Section 6.2. Remember to write down all vocabulary, take notes 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: 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.
• Talk with your group about which presentation spot you want. Rank the six spots in order of preference. The options are Tuesday, April 23rd at 10:20, Tuesday, April 23rd at (roughly) 11:05, Thursday, April 25th at 10:20, Thursday, April 25th at (roughly) 11:05, Thursday, April 30th at 10:20, and Thursday, April 30th at (roughly) 11:05. We will finalize times on Thursday. If you are not prepared with your list, your group will forfeit your choice.

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

• Exercises 5.20 (think carefully how you prove this), 5.26 (Hint: You are allowed to use anything you have already proved including on previous assignments!) (pages 122-123) and 5.28(a)-(e) (pages 122-123).
• 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 problem that was due March 8 (Final Chance: April 5) and March 29 (Final Chance: April 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. Review our Notebook Problem Set Policy and be sure that you do at least one resubmission for each Notebook problem!

### WEEK 9: March 25 - March 29

Have a great spring break!!!

Due to an appointment on Monday afternoon, my Monday office hours will be moved to Tuesday for this week. My hours will be Tuesday, March 26th, 1:00pm-2:00pm. My hours for the rest of the week (Wednesday, Thursday and Friday) will be normal.

There will be no quiz this week!

Remember that Monday, March 25 is your final chance to resubmit the Notebook Problems from Week 4 (originally due February 15) and Week 5 (originally due February 22). Submit them in the box by my office by 3:30pm. Remember that you must turn in your earlier draft(s) with any resubmission. Review our Notebook Problem Set Policy and be sure that you do at least one resubmission for each Notebook problem!

Reading and Practice Problems for class Tuesday, March 26:

• Review your work on the Connectivity group work handout. We discussed much of it, but go back and finish any parts you did not and be sure that the concepts make sense. Bring any remaining questions you have to class.
• Reread Section 5.3 (pages 115-121)! Make sure you have done these things from the previous assignment: 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.11, Whitney's Theorem that we will prove in class. Note the discussion of Harary graphs, which we first learned about on page 39.
• I will be looking for volunteer to present a proof for Exercise 13 on the Connectivity group work handout. Here is an example of how we might be interested in proving things about $k$-connected graphs!
• Complete the following exercises: 5.25, 5.27, 5.29 and 5.31 (pages 122-123).
• Practice Problem: 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.

Article Project: Definition Assignment (Due Wednesday, March 27 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 already 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 example 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 28:

• Review our work on connectivity, particularly on Whitney's theorem. Make sure you understand why each part of the proof was necessary. Reread Section 5.3 and check out some of the other theorems in the text!
• Read Section 5.4 (pages 124-129). Work through the proof of Menger's Theorem. We will prove 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, March 29 by 3:00PM):

• Exercises 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 three non-isomorphic connected graphs with six vertices, six edges, and three blocks. You need not explain why your graphs work.
• How many non-isomorphic connected graphs are there with seven vertices, seven edges, and three blocks? Justify your answer. (Hint: think about partitions.)
• 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 problem that was due March 1 (Final Chance for this one!) and March 8 (Final Chance: April 5). 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. Review our Notebook Problem Set Policy and be sure that you do at least one resubmission for each Notebook problem!

Optional BONUS Assignment (Due Tuesday, April 2 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, you may NOT use the internet nor any other resources. Turn these in separately from your other homework. Since this is bonus, these proofs must be very high quality in order to earn points.
• Problem 4.30 on page 100 of your text.
• BONUS 2 from your midterm exam. (Note: you may assume $G$ is connected.)

### WEEK 8: March 11 - March 15

Check your email late Sunday afternoon for a message from me with possible exam questions. Remember that you should treat these as a take home exam. You may discuss these with me and you may use your book and notes, but you may not use any other resources animate or inanimate. At least one of these questions (probably two) will be on the midterm.

Due to our midterm exam, there will be no quiz and no collected homework or notebook problem 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 14th during class time. However, we will not be in our regular classroom! The midterm will be in Demarest 117A. The exam will cover 1.1-1.4, 2.1-2.3, 3.1, 3.2, 4.1-4.3, 5.1 and 5.2.

Reading and Practice Problems for class Tuesday, March 12:

• Review your work on connectivity in Thursday's class. Continue working on the questions you did not get to within your group, and try to attempt all questions 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.)
• 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! :-)
• Near the end of class, I will be looking for volunteers to present Exercise 2.13 and Exercise 5.7 as part of our review for the exam.

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

• Together with your project team, 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 the article, as well as the first two pages of the article. Designate one person in your group to email me your list.

Reading and Practice Problems for class Thursday, March 14:

• 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! :-)
• Remember that the exam will be in Demarest 117A and there will be randomized seating. See you there!

Article Project: Introductory Assignment (Due Friday, March 15 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, but the whole team should be participating in the completion of this assignment. 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. Part of this assignment can be done before you have been assigned your article!
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) or from arXiv. 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 is an article on the list that you can not obtain from MathSciNet or arXiv. If you discover that yours is the one, 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? Who are they and what articles have they written?
5. What are author citations? Explain in your own words.
6. What do you find when you look for author citations for Michael Pelsmajer? What information does this give you? How is Dr. Pelsmajer connected to me?

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 8 (Note: for part two it is sufficient to just show ONE way; Final Chance for this one!!!), February 15 (Final Chance: MONDAY, March 25), February 22 (Final Chance: MONDAY, March 25), March 1 (Final Chance: March 29) and March 8 (Final Chance: April 5). 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. Review our Notebook Problem Set Policy and be sure that you do at least one resubmission for each Notebook problem!

### WEEK 7: March 4 - March 8

Quiz 6 will be on Tuesday, March 5 covering last week's material (Sections 4.3 and 5.1).

Reading and Practice Problems for class Tuesday, March 5:

• Nice class discussions and research into cut-vertices last Thursday! Keep up the good work!
• Work on proofs for the theorem about cut-vertices and complements that we were discussing at the end of class on Thursday. Try to work out the end of the proof of the version I was presenting when class finished, and also work out the details for Sam's approach.
• 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.
• Read Section 5.1 (pages 107-110). Some of the theorems (and their proofs!) we came up with in class are in here. Do they make sense? Remember to write all vocabulary, take notes 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: 5.1, 5.3, 5.5 and 5.7 (pages 110-111).

Reading and Practice Problems for class Thursday, March 7:

• Review the two proofs about complements and cut-vertices that we discussed. Come up with a good proof of the lemma that states that the complement of $G-v$ is the same as deleting $v$ from the complement of $G$.
• Review our group work on blocks from class on Tuesday. 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). Do you see some of your conjectures here? Make sure the proofs of the theorems and corollary make sense. Remember to write all vocabulary, take notes 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.
• I will be looking for volunteer to present Exercise 5.7 (page 111). You should solve it before looking at the book's solution. A final solution will fill in the steps that the book's solution skips (or be completely different!). You do not need to speak with me ahead of time in order to present, but I am happy to discuss it with you. If there is more than one volunteer, we will roll a die to see who presents.
• Complete the following exercises: 5.9, 5.11 and 5.13 (page 114).

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

• Exercises 4.20 (page 94) and 5.2 (page 110).
• Exercise: Label the edges of the wheel $W_7$ with the weights $1,1,2,2,3,3,4,4,5,5,6,6$ in such a way that the number of minimum weight spanning trees is (a) one, (b) more than one. Briefly explain why your labelings work; include spanning trees.
• Complete the exercise on this worksheet. Some copies of this worksheet can be found in a box outside my office. I can print more if needed.
• Notebook Problem: Exercise 4.26 (page 99). (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 8 (Note: for part two it is sufficient to just show ONE way; Final Chance: March 15), February 15 (Final Chance: MONDAY, March 25), February 22 (Final Chance: MONDAY, March 25), and March 1 (Final Chance: March 29). 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 25 - March 1

Due to visiting another professor's class, my Friday office hours this week will be moved to 1:30-2:30. Let me know if you cannot make my office hours this week and have questions. Plan ahead!

Quiz 5 will be on Tuesday, February 26 covering last week's material (Sections 4.1-4.3).

Reading and Practice Problems for class Tuesday, February 26:

• Review your fourth 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. Make sure you have a list of edges as a result of using Kruskal's algorithm and a list as a result of using Prim's algorithm (questions 5 and 6 on the hand out). Think of similarities and differences between the two algorithms.
• Reread Section 4.3 (pages 94-99). Pay special attention to the proofs that the algorithms DO produce minimum weight spanning trees.
• Complete the following exercise: 4.22 (page 94), 4.25 (page 99).
• Take two: I will be looking for a volunteer to present exercise 4.23 (page 93). You should solve it before looking at the book's solution. A final solution will fill in the steps that the book's solution skips.

Article project group choice (Due Thursday, February 28 by 3:00pm):

Discuss with your classmates who would like to work together for the article project. Find a group of three, have one of your group members email me and let me know you will be working together. Having trouble finding a group of three? Let me know and I will help!

Reading and Practice Problems for class Thursday, February 28:

• Hang in there! We have had some good class discussions and you have lots of great ideas! Remember that this is a 300-level course so it will be challenging, but you can do it! I would really love to see more of you in office hours more regularly! Graph theory is so neat! LIVE it!
• 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.
• Reread Section 4.3 (pages 94-99). Pay special attention to the proofs. Theorem 4.11 is the theorem we were proving Tuesday 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).

Check out the Notebook Problem Set Policy here. If anything is unclear or you have any questions, please do not hesitate to ask.

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

• Exercises 4.6 (page 87), 4.12 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 (b) (page 94). (This part is figuring out how to generalize part (a) and then proving it! Cool! I recommend trying part (a) first, but just turn in part (b).) (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 8 (Note: for part two it is sufficient to just show ONE way; Final Chance: March 15), February 15 (Final Chance: MONDAY, March 25) and February 22 (Final Chance: MONDAY, March 25). 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 18 - February 22

Quiz 4 will be on Tuesday, February 19th covering last week's material (Sections 2.4, 3.1, 3.2 and 4.1).

Reading and Practice Problems for class Tuesday, February 19:

• Great research in class on Thursday! You came up with many conjectures and were able to give good arguments (proving and disproving) for many of them!
• 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.
• 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, remember that 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. We have done one example and the proof of Theorem 4.7 on page 91 is another 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).

Due to an appointment, my Friday office hours this week will be moved to 1:30-2:30. Let me know if you cannot make those and have questions. Don't wait until then to ask major questions about the homework!

Reading and Practice Problems for class Thursday, February 21:

• Review our classwork on proving TFAE theorem about trees. Work on the induction we began and figure out the next few steps.
• 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!!!
• Read Section 4.3 (pages 94-99). Remember to write all vocabulary, take notes 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: 4.11, 4.17, 4.19, 4.21 and 4.23 (pages 93-94).
• After Taylor completes her presentation, I will be looking for another volunteer to present exercise 4.23 (page 93). You should solve it before looking at the book's solution. A final solution will fill in the steps that the book's solution skips.

Collected Assignment (Due Friday, February 22 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 8 and February 15. 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 11 - February 15

Remember that resubmissions of the Notebook problem that was due Friday, February 1st are due no later than Monday, February 11th 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.

Quiz 3 will be on Tuesday, February 12th covering last week's material (Sections 2.1-2.3).

Reading and Practice Problems for class Tuesday, February 12:

• 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 to present a solution to Exercise 2.22! (Note that you were assigned Exercise 2.22 as a practice problem for last Thursday!) Since the solution will use Theorem 2.7 and its proof in part of the answer, be sure you can remind the class what the statement of the theorem is. You are encouraged to speak with me ahead of time about this and you may bring your notes (though not your text) to the board.
• Reread Section 2.3 (pages 43-47). Does this material make sense? Bring questions to class or office hours.
• 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).
• Read Section 2.4 (pages 48-49). This section is short! Remember to write all vocabulary, take notes 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.
• Read Sections 3.1 and 3.2 (pages 55-65), paying special attention to the proof of Theorem 3.6 on page 64. We have been throwing around the term "isomorphism", now we can make it more precise! Remember to write all vocabulary, take notes 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.

Reading and Practice Problems for class Thursday, February 14:

• Review our classwork on adjacency matrices and isomorphisms. Reread Sections 1.4 and 3.1 and bring any questions you have on either to class or office hours.
• Read Section 3.2 (pages 63-65), paying special attention to the proof of Theorem 3.6 on page 64. Refresh your memory from MATH 135 of equivalence relations! Remember to write all vocabulary, take notes 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.
• 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. Be sure that you read the very short Section 4.1 before you read this one!
• Complete the following exercises: 2.39 (page 50), 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!
• Read Section 4.1 (pages 85-87) about bridges. Remember to write all vocabulary, take notes 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: 4.1 and 4.5 (page 87).

Collected Assignment (Due Friday, February 15 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.8 on pages 37 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 problem that was due Friday, February 8th. Remember that you must turn in your first draft with any resubmission.

### WEEK 3: February 4 - February 8

Quiz 2 will be on Tuesday, February 5th covering last week's material (Sections 1.3 and 2.1).

Reading and Practice Problems for class Tuesday, February 5:

• Review your first quiz and my comments. Bring any remaining questions you have on it to office hours.
• Review our proofs of Theorems 1.11 and 1.12 (the bipartite characterization theorem). Make sure they make sense and you understand why each step is important. 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.
• Complete the following exercises: 1.23, 1.29 and 1.33 (pages 25, 28-29 and 29 respectively).
• Reread Section 2.1 (pages 31-36). Note the discussion of sharpness on page 35.
• Finish the degrees handout from class. Bring questions and be ready to share your results in class on Tuesday. If you can, meet with your group outside of class to discuss any problems you did not already discuss in class.
• 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.
• Read Section 2.2 (pages 38-41). It's a short section! 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!!! Remember to write all vocabulary, take notes 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.

Reading and Practice Problems for class Thursday, February 7:

• Read my comments on your notebook problem. Make sure they all make sense. Bring any questions to me and start reworking the notebook problem. Think carefully about whether you need to restructure or just revise your original proof. Remember that you may not discuss these with others, but you are highly encouraged to discuss them with me!
• Review our proof of Theorem 2.4. Recall you were to focus on the discussion (in relation to this theorem) of sharpness on page 35. Can you explain what it means for a bound to be sharp? Be ready to discuss this in class.
• Reread Section 2.2 and bring any questions you have on it with you to class. Note that our group work on degrees covered many of the ideas in this section.
• 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.3 (pages 43-47). Remember to write all vocabulary, take notes 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: 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 (Haixin and Peter should especially like this one!) and 2.22 (page 42). Note that Exercise 2.22 helps illustrate Theorem 2.7.
• I will be looking for a volunteer to present a solution to Exercise 2.7 (originally assigned for Tuesday). This will count towards your formal presentation as discussed in the syllabus. Recall that there are drafts of solutions to odd questions in the back of the text, but you should solve (hopefully you already did this for Tuesday!) this first before checking, and you will need to fill in some details. You are encouraged to speak with me ahead of time about this and you may bring your notes (though not your text) to the board.

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

• Exercise 1.24 on page 25 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 and not stapled to your other homework, and (2) notebook problems must be done on your own.).
• You may also resubmit the Notebook problem that was due Friday, February 1st. Remember that you must turn in your first draft with any resubmission. If you wish to resubmit this problem you must do so no later than Monday, February 11th 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 28-February 1

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

Reading and Practice Problems for class Tuesday, January 29:

• Review the Traversability group 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 write all vocabulary, take notes 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: write an outline and note. Also do exercise 1.21 on page 25.

Reading and Practice Problems for class Thursday, January 31:

• 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.
• Review the work we did on proving Theorem 1.11 in class. Think about how to finish it withOUT looking at the proof in the text. Be ready to share your thoughts on Thursday. Also take a look at the proof of Theorem 1.12 about bipartite graphs. This is a very important theorem!
• Read Section 1.4 (pages 26-28) for a brief introduction to non-simple graphs: multigraphs and digraphs.
• Read Section 2.1 (pages 31-36) -- finally the term "degree"! Remember to write all vocabulary, take notes 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.
• This will be an ongoing project: Meet with your fellow pet owner (if you have one) and 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). Add the facts you discovered in class beneath your diagrams. Think of other questions you could ask. I will let you know on what days you should bring these to class. You do NOT need to bring them on Thursday. You should set up a plan with your fellow pet owner to meet regularly to add to this poster.
• 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, February 1 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. (Note that this exercise is asking you to find three different graphs!)
• 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 22-25

Welcome to Graph Theory!!!

Collected Homework (Due Wednesday, January 23 at 3:00pm):

• Write an autobiographical essay as assigned on the syllabus. There is a box outside my office where you can put the essay if I am not in my office.

Reading and Practice Problems for class Thursday, January 24:

• 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, and be ready to share your work on the board and verbally.
• Read Section 1.1 (pages 1-7) and Section 1.2 (pages 9-17) in your text. The first section reviews the definitions we discussed in class and gives you some ideas about applications of graph theory. The second section introduces you to some new definitions in graph traversibility and interesting related theorems and ideas. 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 this 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.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 25 by 3:00PM):

Be sure to read the directions, both in the assignment below and in the text, very carefully. You may submit this assignment in person or place it in the box outside my office.
• 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, that is, in graph theory terms.
• Draw all distinct graphs on four vertices. (This is number 3 from the group-work sheet from class. Hint: There are more than eight and less than 15 such graphs.) You need not justify why you have found them all.
• Exercise 1.12 on page 17 of our text. Describe carefully in graph theoretic terms (i.e. use your definitions!) why each example satisfies the requirements or why you can find no such example.
• There will be no Notebook problems due this week!

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