Math 371 - Spring 2010
Topics in Mathematics - Graph Theory

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

Office Hours: M 10:30am-Noon, W 3:00-5:00pm, Th 3:00-4:00pm, F 1:30-2:30pm and by appointment
Class Schedule: held TTh 10:20-11:45 in Lansing 301
Course Syllabus
Proof Writing and Presentation Tips
Course Grade Scale

READING/EXAM WEEK

Reading and Practice Problems:

• Read Sections 10.1, 10.3 and 10.4.
• Complete the following exercises: 10.13 (page 279), 10.17 and 10.19 (pages 287-288).

Review Session: Friday, May 7th 2:00PM-3:00PM in Lansing 301. Bring questions! Remember I will be looking for three volunteers to present 10.5 (page 240), 6.12 (page 151) and 5.7 (page 111). These will be a good review. Remember that presentations should include definitions and some sort of visual diagram. Remember if none of the people who haven't presented a second time claim the problem, those who have can get bonus points for doing extra presentations!

Office Hours:

• Wednesday, May 5th: 2:30PM-5:00PM
• Thursday, May 6th: 2:00PM-4:00PM
• Friday, May 7th: 3:00PM-4:30PM
• Monday, May 10th: 1:30PM-3:30PM
• By appointment

Final Exam: Tuesday, May 11th 9:00AM-NOON in Lansing 301.

WEEK 15: May 3-4

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

REMINDER: Please turn in your Self/Partner Evaluation by class on Tuesday. Remember these should be your own thoughts -- this is not a collaborative assignment.

Reading and Practice Problems for class Tuesday, May 4:

• Read Section 10.2.
• Complete the following exercises: 10.1, 10.5, 10.7, 10.9, 10.12 (pages 277-279).
• I will be looking for three volunteers to present 10.5 (page 240), 6.12 (page 151) and 5.7 (page 111). These last two should help us review some concepts from earlier in the semester. Remember that presentations should include definitions and some sort of visual diagram. Remember if none of the people who haven't presented a second time claim the problem, those who have can get bonus points for doing extra presentations!

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

• Prove that if G is a planar graph with at least 11 vertices, then the complement of G is nonplanar.
• Prove that there does not exist a connected plane graph that has seven regions and all vertices of degree four.
• Complete exercise 9.26 (page 248).
• Complete exercise 9.28 (page 249). Note that the problem should say Theorem 9.12 not Theorem 10.15 in the introduction. 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 and 10.6 (pages 277-8).
• 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 this in on a separate piece of paper from your other homework, and (2) notebook problems must be done on your own.
• BONUS (10 points): Redo problem 5.30 (page 124). I will be looking for very precise and concise proofs. Treat this problem as a Notebook Problem. There should be no collaboration.
• You may also resubmit the Notebook problems that were due April 2, April 9 or April 16. Remember that you must turn in your earlier draft(s) with any resubmission.

WEEK 14: April 26-30

I will be participating in an honors oral exam during my regular office hours on Thursday, April 29. Thus I will be moving my office hours earlier. Office hours on Thursday, April 29 will be 1:30-2:30. Please let me know if you have questions and feel free to email me.

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

REMINDER: your final paper is due MONDAY, APRIL 26 by 5:00PM.

Reading and Practice Problems for class Tuesday, April 27:

• Work on filling in the blanks in the handout from class.
• Finish reading Section 9.1 (pages 227-238). Can you find the mistake on page 238?
• Start reading Section 9.2.
• Complete the following exercises: 9.5, 9.7, 9.11, 9.13(c) and 9.15 (pages 239-240).
• I will be looking for a volunteer to present 9.15 (page 240). The presentation should be refined and include all details.

Reading and Practice Problems for class Thursday, April 29:

• Decide by Wednesday, April 28 at 4:00pm if you would like another day to revise your paper based on the comments you received on your presentation.
• Finish reading Section 9.2 (pages 241-248).
• Complete the following exercises: 9.19 (page 241; the definition of maximal is on page 233); 9.23, 9.25 and 9.27 (pages 248-249; note, as is often the case, the answer for 9.25 is incomplete).
• Here is an exercise based on 9.17 (page 241): (a) Show the complement of C_n is nonplanar for n at least 8 using Corollary 9.3 and Theorem 9.2. (b) Show that the complement of the cycle on seven vertices satisfies the inequality in Theorem 9.2 and yet the graph is nonplanar. I will be looking for a volunteer to present this problem.

WEEK 13: April 19-23

Due to the in-class presentations this week and the fact that your final paper is due MONDAY, APRIL 26, there will be no quiz this week and no collected assignment. Work on making your presentations and papers top quality, redo some notebook problems and catch up on your practice problems.

Due to a family committment, I will need to cancel my office hours on Thursday, April 22. Try to use my office hours earlier in the week, but if you need to see me on Thursday, talk to me about making an appointment earlier in the day. Please let me know if you have questions and feel free to email me.

Reading and Practice Problems you should be working on:

• Note that you should be taking notes and actively involved during the presentations in class, as you will likely be asked a question on the final exam that has to do with another group's presentation.
• Start reading Section 9.1.
• Complete the following exercises: 9.1 and 9.3 (page 238).

Presentations in class Tuesday, April 20:

• Trevor Gionet and Isabel Olson: "On the well-coveredness of Cartesian products of graphs."
• Jillian Harris and Karina Polanco: "Vertex-magic labeling of trees and forests."

Presentations in class Thursday, April 22:

• YoYo Cao and Shaun Viguerie: "Roman k-Domination in Graphs."
• Prof. King!: more on planar graphs and graphs on other surfaces

Although there is no regular collected assignment due Friday, you may resubmit the Notebook problems that were due March 26 (last chance for this one!), April 2 or April 16. Remember that you must turn in your first draft(s) with any resubmission.

WEEK 12: April 12-16

Quiz 9 on Tuesday, April 13th covering Sections 6.1 and 6.2 (as covered in class).

Reading and Practice Problems for class Tuesday, April 13:

• Read Section 6.1 (pages 133-139) and start reading Section 6.2.
• Complete the following exercises: 6.7 (page 140), 6.9 (page 150).

Article Project: Rough Draft Assignment (Due Tuesday, April 13 by 5: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 Thursday, April 15:

• Read Section 6.2 (pages 140-150).
• Complete the following exercises: 6.11, 6.13, 6.15, 6.19 and 6.21 (pages 139-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 16 by 3:00PM):

• Exercises 6.2, 6.4, (pages 139-140), 6.10 (page 150).
• Exercise 6.24 (page 152).
• Notebook Problem: Exercise 6.16 (page 151). Remember: (1) Turn this 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 March 26 or April 2. Remember that you must turn in your earlier draft(s) with any resubmission.

WEEK 11: April 5-9

Quiz 8 on Tuesday, April 6th covering Sections 5.3 and 5.4.

Reading and Practice Problems for class Tuesday, April 6:

• Remember to be working on your article project rough draft.
• Finish reading Section 5.4 (pages 124-129).
• Complete the following exercises: 5.35 (page 129).

Reading and Practice Problems for class Thursday, April 8:

• Start reading Chapter 6.
• Complete the following exercise: 6.1, 6.5 and 6.6 (pages 139-140).
• I will be looking for a volunteer to present 6.6.

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

• Construct a graph that has equal vertex and edge connectivity such that this value is not equal to the minimum degree. Justify your graph.
• Construct a graph whose edge connectivity equals its minimum degree such that this value is not equal to the vertex connectivity. Justify your graph.
• Construct a graph that is not complete such that its connectivity, edge connectivity and minimum degree all equal four. Justify your graph.
• Let G be a connected graph with at least three vertices. Form G' from G by adding an edge with endpoints x, y whenever the distance between x and y equals 2. Prove that G' is 2-connected.
• Exercise 6.14 (page 151). Look! It is Trevor's question!
• Notebook Problem: Exercise 5.36 (page 129). Remember: (1) Turn this 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 March 26 or April 2. Remember that you must turn in your earlier draft(s) with any resubmission.

WEEK 10: March 29-April 2

Since there is a colloquium at 4 on Wednesday, my office hours on Wednesday, March 31 will start earlier and be from 2:00 until 3:45. My office hours on Friday, April 2 will also be moved slightly later to 2:00-3:00. As usual, if you cannot make these times and have questions, please contact me to make another appointment.

Quiz 7 on Tuesday, March 30th covering Sections 5.2 and 5.3.

Reading and Practice Problems for class Tuesday, March 30:

• Read the article project handout and make sure you have no questions about what is expected.
• Read Section 5.3 (pages 115-122).
• Complete the following exercises: 5.21, 5.25, 5.27, 5.29 and 5.31 (pages 122-124).

Article Project: Outline Assignment (Due Wednesday, March 31 by 5: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 likely be Friday, April 2, Monday April 5 or Wednesday, April 7. 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 Thursday, April 1:

• Start reading Section 5.4. Spend a little time with the proofs. We will be proving Theorem 5.21 in class.
• Complete the following exercise: 5.33 (page 129).
• 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. Don't assume someone else will present! Be prepared! Time is running out!

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

• 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 124).
• Notebook Problem: Prove: If the diameter of G is less than or equal to 2, then the edge-connectivity of G is equal to the minimum degree of G. Remember: (1) Turn this 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 March 5 (last chance for this one) or March 26. Remember that you must turn in your earlier draft(s) with any resubmission.

WEEK 9: March 22-26

Have a Great Spring Break!!!

I will be leaving for a conference on Friday, March 26th and so will not be able to have office hours Friday afternoon. Please plan ahead and get your questions answered earlier in the week.

There will be no quiz this week!

Reading and Practice Problems for class Tuesday, March 23:

• Read Section 5.2 (pages 111-114). Make sure the proofs of the theorems and corollary make sense.
• Complete the following exercises: 5.9, 5.11 and 5.13 (page 114).

Article Project: Definition Assignment (Due Wednesday, March 24 at 5: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 groups 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.

Reading and Practice Problems for class Thursday, March 25:

• Work on the handout from Tuesday's class. Review the answers to the questions you completed in class and complete the questions you did not yet. We will discuss this as a class on Thursday. Be ready to share your answers and ask any questions you have.
• I will be looking for a volunteer to present number seven from the worksheet. Don't assume someone else will do it! Be prepared!
• Complete the following exercises: 5.17 and 5.19 (page 122).

Collected Assignment (Due Friday, March 26 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.
• Exercise 5.18 (page 122).
• 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 this 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 26 (last chance for this one) or March 5. Remember that you must turn in your earlier draft(s) with any resubmission.

WEEK 8: March 8-12

There will be no quiz and there will be no collected homework assignment due this week!

Our Midterm Exam will be on Thursday, March 11th 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 9:

• Great class last Thursday! Keep up the good work!
• Read Section 5.1 (pages 107-110). Make sure the proofs of the theorems make sense. They prove several theorems that we discussed but did not prove in class.
• Complete the following exercises: 5.1, 5.3, 5.5 and 5.7 (pages 110-111).
• I will be looking for a volunteer for 3.13 as part of our review for the exam. 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.

Reading and Practice Problems for class Thursday, March 11:

• Individually, work on the questions from the review sheet. Come to office hours if you have any questions.
• 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 12 at 3:00PM):

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 an extra copy/print out of your article and turn it in as part one of this assignment.
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 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 of that other paper.
   3. Are there any mathematicians or scientists with your last names?
   4. What are author citations?
   5. 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 may resubmit the Notebook problems that were due February 12 (last chance for this one!), February 26 or March 5. Remember that you must turn in your first draft(s) with any resubmission.

WEEK 7: March 1-5

NOTE: Office hours on Thursday will be moved to 2:15-3:15. Please let me know if you would like to meet and cannot make that time.

Quiz 6 on Tuesday, March 2nd covering last week's material (Section 4.2).

Reading and Practice Problems for class Tuesday, March 2:

• Without reading your book, work on questions 1-3 on Thursday's groupwork sheet. Be ready to report to your group on Tuesday.
• Finish reading Section 4.2 (pages 87-92). Carefully review the proof of Theorem 4.9 on page 92.
• Complete the following exercises: 4.11, 4.13, 4.19, 4.23 (pages 93-94).

Article project choice list (Due Wednesday, March 3 by 5:00PM):

• Together with your project partner, make a list of your top three or more choices of articles.

Reading and Practice Problems for class Thursday, March 4:

• Start reading Section 4.3.
• Complete the following exercises: 4.25, 4.26 and 4.27 (pages 99-100).
• I will be looking for a volunteer to present 4.26. Please don't force me to start handing out zeros.

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

• Exercises 4.10, 4.20 and 4.22 (pages 92-94).
• Complete the exercise on this worksheet.
• Notebook Problem: Let G be a connected graph. Prove: If u, v and w are vertices of G, then d(u,v)+d(v,w)>=d(u,w). That is, (rigorously!) prove that the distance function for graphs satisfies the triangle inequality. (Remember: (1) Turn this 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 (last chance for this one), February 12 or February 26. Remember that you must turn in your earlier draft(s) with any resubmission.

WEEK 6: February 22-26

I will be unable to hold my regular office hour this Thursday. Instead I will be available from 11:50am until 12:35pm that day. Please let me know if you would like to meet and cannot make that time.

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

Reading and Practice Problems for class Tuesday, February 23:

• Read Sections 3.1 and 3.2 (pages 55-65), paying special attention to the proof of Theorem 3.6, and Section 4.1 (pages 85-87).
• Find two non-isomorphic graphs with the degree sequence: 4, 2, 2, 1, 1, 1, 1. Justify why the graphs are non-isomorphic.
• Complete the following exercises: 3.13 and 3.15 (page 63), 3.17 and 3.18 (page 65), 4.1 and 4.3-4.5 (page 87).
• 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. The presentor is expected to give an overview, remind people of definitions, explain each step and be prepared to answer questions.

Reading and Practice Problems for class Thursday, February 25:

• Complete your survey and bring it to class. On a separate piece of paper, order the people in the class with the first person being the one with whom you would most like to work on the article project. There should be three or four people in this list. I realize that I asked you for these before, but now you have spent more time with your classmates and this list should not include the person with whom you worked on the applied project.
• Read Section 4.2 (pages 87-92).
• Complete the following exercises: 4.7, 4.9, 4.12, 4.15 (pages 92-93).
• I will be looking for a volunteer to present exercise 4.12 (page 93). Give two examples for part (a) and be sure to have a rigorous argument for (b). If there are no volunteers, I will choose someone randomly.

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

• Exercises 2.32 (page 47), 3.10 and 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 37), and 4.6 (page 87).
• Exercise 4.14 (page 93).
• Notebook Problems: Exercises 4.8 and 4.16 [Be sure you justify you have found all such graphs in 4.16 (b)] (pages 92-93). (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 January 29 (last chance for this one), February 5 or February 12. Remember that you must turn in your earlier draft(s) with any resubmission.

WEEK 5: February 15-19

Quiz 4 on Tuesday, February 16th covering last week's material (Sections 2.1-2.3 and trees).

Reading and Practice Problems for class Tuesday, February 16:

• Read Section 2.2 (pages 38-41) and start reading Section 2.3. Check out Harary graphs (page 39). Frank Harary was my academic grandfather...and quite a character!
• Complete the following exercises: 2.23, 2.24 (Note that to show 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.29 and 2.33 (pages 42, 43 and 47).

Reading and Practice Problems for class Thursday, February 18:

• Read Sections 2.3 and 2.4 (pages 43-49). Start reading Section 3.1.
• Complete the following exercises: 2.31 and 2.35 (page 47), 2.39 (page 50), and 3.1-3.3, 3.7 (pages 61-62).
• I will be looking for a volunteer for Exercise 3.2 on page 61. A presentation should include nice pictures and clear explanations.

Applied Graph Theory Project Due Friday, February 19 by 3:00PM

Although there is no regular collected assignment due Friday, you may resubmit the Notebook problems that were due January 29, February 5 or February 12. Remember that you must turn in your first draft with any resubmission.

WEEK 4: February 8-12

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

Reading and Practice Problems for class Tuesday, February 9:

• WithOUT looking in your textbook, just using the handouts from class, come up with at least one more conjecture about trees. It doesn't have to be elaborate. Before class begins on Tuesday, put your conjectures on the white board. This means there should be at least six conjectures on the board (it is ok if you happen to have the same one as someone else, but if you work together you should come up with a different one for each person in the group).
• Read Section 2.1 (pages 31-36).
• Complete the following exercises: 2.1, 2.5, 2.7 (pages 36-37).

Reading and Practice Problems for class Thursday, February 11:

• Great conversations going on in class on Tuesday! Continue working on the groupwork sheet from Tuesday's class. We will have each group present their work. The YoYo-Shaun-Isabel group will talk about number 1 (so you can start putting up graphs as soon as you get to class), and the Trevor-Karina-Jillian group will talk about numbers 2 and 3. Good work everyone!
• We will return to trees in the near future. Keep thinking about them. Work on proving that "every nontrivial tree has at least two leaves". As with many things, there are many ways to prove this. Try directly and by induction. Also, can you prove or disprove Karina's conjecture?
• Complete the following exercises: 2.13, 2.15, and 2.18 (pages 37-8), and 2.21 (page 42).
• I will be looking for a volunteer for Exercise 2.18 on page 38.

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

• Exercises 2.2 and 2.4 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.)
• Exercise 2.8 on page 36 in our text. Be sure to explain your examples.
• 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.
• Notebook Problem: Exercise 2.10 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 January 29 or February 5. Remember that you must turn in your first draft with any resubmission.

WEEK 3: February 1-5

TO BE TURNED IN ON TUESDAY: You will be doing a short project (over two weeks beginning this Friday) and a long project (over the second half of the semester) this semester. Each of these will be done in pairs. Preferably, you will have a different partner for each project. Please make two lists, one for the short project and one for the long, which list your preferences for partners with the first in the list being your top choice. Be sure that you have at least three in each list.

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

Reading and Practice Problems for class Tuesday, February 2:

• Read Section 1.2 (pages 9-17) in your text again. Pay special attention to the Theorems we did not discuss in class (1.7-1.9) and their proofs, especially Theorem 1.7 with equivalence relations (remember those?!). Start reading Section 1.3 (especially pages 19-21).
• I will be looking for a volunteer to present exercise 1.17 (page 18). This is an exercise that was due last Thursday. Please be prepared to present it to the class.
• Complete the following exercises: 1.22, 1.24 and 1.25 (page 25).

Reading and Practice Problems for class Thursday, February 4:

• Read 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. Start reading Section 2.1.
• I will be looking for a volunteer to present exercise 1.17 (page 18). This is an exercise that was due last Thursday. Please be prepared to present it to the class.
• Finish the group worksheet from class. List any questions you have.
• Complete the following exercises: 1.21, 1.33, 2.3 (pages 25, 29, and 36 respectively).

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

• Exercise 1.26 on page 25 in our text.
• Prove that removing opposite corner squares from an 8-by-8 checkerboard leaves a subboard that cannot be partitioned into 1-by-2 and 2-by-1 rectangles. Using the same argument, make a general statement about all bipartite graphs.
• Exercise 1.27 on page 26 of our text.
• Complete Problem 6 from your group worksheet; that is, prove the First Theorem of Graph Theory using induction.
• 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.

WEEK 2: January 25-29

You will sign up for appointments on Tuesday. Please remember to keep them!!!

Note that some of your individual appointments are scheduled during part of my Wednesday office hours, so my open office hours on Wednesday are slightly different this week; they are 3:30-5:00.

I will need to leave early on Friday to take care of my sons, so I will need to move my office hours on Friday. They will be from 11:00am until noon. Please let me know if you need to see me and cannot make this time.

Quiz 1 on Tuesday, January 26th covering last Thursday's class (Section 1.1 and part of 1.2) and your definition worksheet. Remember that you will be allowed to have your definition worksheet during the quiz.

Reading and Practice Problems for class Tuesday, January 26:

• Read the syllabus. Even though we discussed this, you should make sure you are clear on all the policies and expectations.
• 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.
• Complete the groupwork sheet from class. Bring any questions you have on this to class.
• Read Section 1.1 (pages 1-7) and start reading Section 1.2 (pages 9- the top of page 14) in your text. Remember to fill out your definitions worksheet, keep track of any other vocabulary and jot down example graphs to help you understand the concepts.
• Complete the following practice problems: 1.3 (page 7), 1.7 (page 8), 1.10 (page 9), 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!

Reading and Practice Problems for class Thursday, January 28:

• Make sure that the Traversability group worksheet from class makes sense. We will discuss the last question in class together with any other thoughts you bring.
• Finish reading Section 1.2 (pages 11-17) in your text. Remember to keep track of vocabulary and jot down example graphs to help you understand the concepts.
• Complete the following exercises: 1.13, 1.17 and 1.18 (page 18) from your textbook.

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.
• Notebook Problem: Exercise 1.16 on page 18 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.).

WEEK 1: January 20-22

Welcome to Graph Theory!!!

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

• Write an autobiographical essay as assigned on the syllabus.
• On a separate paper from your essay, complete the following exercises:
  1. Exercise 1.4 on page 7 of our text. Show your work, not just the final drawing.
  2. Draw all distinct graphs on four vertices. (This is number 4 from the class groupwork. Hint: There are more than eight and less than 15 such graphs.)
  3. Using the graph G given for question 5 on your class worksheet answer the following:
     1. Draw a subgraph of G that is spanning and proper. Explain why your graph fullfills the requirements.
     2. Draw a subgraph of G that is proper and induced. Explain why your graph fullfills the requirements.
     3. Draw a subgraph of G that is spanning and induced. Explain why your graph fullfills the requirements.
     4. Draw a subgraph of G that is proper, but not spanning nor induced. Explain why your graph fullfills the requirements.

Last modified: Wednesday 5 May 13:29:07 EDT 2010