MA 111 Spring 2015

Graph Theory


Don't Forget About The Written Project!

Extra Credit opportunities can be found here

Additional Homework

Graph Homework #1--Due: Tuesday April 21

Graph Homework #2--Due: Tuesday April 28

Course Materials

Review Sheet

Review Sheet---Solutions

Graph Homework #1--Solutions

Class Slides

Here are the Graph Theory Slides. They are not divided up by day, so I will make a note here for which slides were covered each day.
April 14th Material
We covered Slides 1-22. (i.e Slide Titled ``New Topic" to the Slide Titled ``Graph Isomorphism") That is, we covered the basic definitions, the 2 theorems on Graph Isomorphisms, and began talking about how to show graph isomorphisms explicitly.
April 16th Material
We covered Slides 22-40. (i.e Slide Titled ``Graph Isomorphism" to the Slide Titled ``Counting Faces and Degrees 2"), however we skipped slides 29 & 30 (i.e. ``Compare with a Neighbor 1 & 2"). We covered how to find graph isomorphisms in more detail, we defined planar graphs, faces, degree of faces, and eluded heavily to (although not yet defining) Euler's Formula.
April 21st Material
We covered Slides 41-65. (i.e Slide titled ``Counting Faces and Degrees 3" to the slide titled ``Vertex Coloring 8"). Specifically, we covered Euler's Formula (connected planar graphs), Euler's General Formula (planar graphs), the basics of vertex coloring, Chromatic number 1 theorem, chromatic number 2 theorem, and the Four Color Theorem.
April 23rd Material
Due to the MiniExam and Course Evaluations, we only covered Slides 64-73. We covered a little more on graph coloring before moving on to Modeling with Graphs, specifically the scheduling problems.
April 28th Material
We covered Slides 73-110. (It was not as much as it sounds like.) We covered modeling maps with graphs, Eulerian Circuits, Eulerian Paths, Eutherian Graphs, Semi-Eulerian Graphs, and associated theorems.
April 30th Material
We covered Slides 111-119. We talked about Eulerizing graphs. Additionally, we reviewed for the Final Exam.