MATH (CSCI) 4690/6690 (Azoff) 
Graph Theory
  Spring 2008

Last updated May 11.

Letter grades have been submitted to the registrar.  Exams may be picked up.

End of term observations and solutions to the final exam can be found at http://www.math.uga.edu/~azoff/courses/4690fnlnotes.pdf

Summaries of material covered during the term and solutions to various homework problems can be found at http://www.math.uga.edu/~azoff/courses/4690notes.pdf

Contents

  • April Schedule
  • Assignments
  • Exams
  • Course Syllabus
    •

    April Schedule

    Date(s) Text Material
    		 Topic
    		 Comments
    W 2 - F 4
    		 Through Chapter 5
    		 Second Hour Test and Discussion
    		 Left to the reader
    M 7
    		 Section 6.1
    		 Edge Cuts
    		 6.6 - 6.8 not emphasized
    W 9
    		 Section 6.2
    		 Connectivity
    		 Excluding Example 6.22
    F 11
    		 Theorem 10.33
    		 Hall's Marriage Theorem
    		 Proof not from text
    M 14
    		 Section 6.5
    		 Menger's Theorems 6.54 - 6.59
    		 Proofs not from text
    W 16
    		 Section 6.4
    		 Flows in Networks
    		 Proof not from text
    F 18
    		 Sections 7.2 - 7.5
    		Planar Graphs
    		 Overview, focusing on Euler's formula
    M 21
    		 Section 8.1
    		 Chromatic Numbers
    		 Excluding Theorem 8.9
    W 23
    		 Section 8.2
    		 Multipartite Graphs
    		 2-colorable = bipartite
    F 25
    		 Section 8.3
    		 Colorings of General Graphs
    		 Focusing on Theorem 8.19
    M 28
    		 Section 8.4
    		 Five Color Theorem
    		 Proof of Theorem 8.28 and statement of Theorem 8.29

    Assignment Summary

    Reading
    		 Problems
    Due
    		 Pages
    		 Hand In
    		 Grad/Bonus
    		 Class Discussion / Extra Practice
    Chapter 1
    		 F Jan 18
    		26-30
    		 5,8,91,10,12,14,16,21,22,24,26,32
    		 1,6,20,34
    		 2,3,4,9,11,13,15,17,19,25,33
    Chapter 2
    		 W Jan 30
    		 61-65
    		 1,4,7,11,13,14,22,24,28,30,34,37
    		 3,6,23,33,40
    		 2,5,8,15,16,21,26,31,32,35,36,38
    Chapter 3
    		 W Feb 20
    		 93-97
    		 2,3,6,7,12,18,22,26,30,34,39,43
    		 4,8,24,41
    		 1,5,9,10,11,13-17,19-21,23,25,27-29,
    31-32,35,37,38,40,42-45
    Chapter 4
    		 F Mar 7
    		 126-131
    		 3,4,102,12,19,20,22,25,30,343,38,41
    		 11,15,32,39,40
    		 1,2,5-9,13,14,16-18,21,23,24,26-29,31,33,39
    Chapter 5
    		 W Mar 26
    		 155-159
    		 1,4,8,14,15,18,26,31,32,40,43,45
    		 6,11,16,21,
    35,42,46
    		 2,3,5,9,17,18,22,27-294,30,33,34,36,37,38,39,41,44
    Chapter 6
    		 F Apr 25
    		 190-192
    		 1,3,12,29,30,A5
    		 6,8
    		 2,4,5,33 (Ford Fulkerson Algorithm not required)
    Chapter 7
    		 229
    		 3,4,7
    		 12,15
    		 5,6,8,11,13
    Hall's Thm
    		 325-326
    		 B5,C5,31
    		 34
    		 30,32,33,34
    Chapter 8
    		259-262

    		1,6,8,12,15,17,21,23,24,31

    5Supplementary Problems

    A  Prove the vertex version of Menger's Theorem:  The maximum number of vertex-disjoint paths connecting two distinct, non-adjacent vertices in a graph G is equal to the minimum number of vertices which need to be removed from in V(G)\{u,v}in order to destroy all uv-paths.

    B  Consider a group X of three girls {a,b,c) and a group Y of three boys {d,e,f,g} of which the following seven pairs are compatible:
    (a,e), (a,f), (a,g),  (b,d), (b,f), (c,d), (c,e).
    i) Draw the corresponding bipartite graph.
    ii) Find five different solutions of the corresponding marriage problem.
    iii) Check that the condition given in Hall's Theorem is satisfied.  

    C A building contractor advertises for a bricklayer, a carpenter, a plumber, and a toolmaker, and receives five applicants -- one for the job of bricklayer, one for carpenter, one for bricklayer and plumber, and two for plumber and toolmaker.  Use Hall's Theorem to decide whether all of the jobs can be filled with qualified applicants.
    1Use Figure 1.15 rather than Figures 1.4 and 1.5.  You will need to assign names to the edges appearing in Figure 1.15.
    2In Chapter 4, you may prefer to work Problems 30 and 31 before Problem 10.
    3It suffices to work the wheel problem (4.34) for the cases n=3 and n=4.
    4Problems 27-29 of Chapter 5 are somewhat more challenging.  "Duplicating an edge" means inserting an additional copy of that edge, parallel to and having the same weight as, the original edge.

    Practice problems should be looked over early, so troublesome concepts can be brought up for class discussion.

    Back to Contents

    Exams

    The final exam was held from Noon - 3 PM on Monday May 5 in our usual classroom;  it was comprehensive.  The median score was 153 of 200.

    Summaries of material     covered during the term and solutions to various homework problems can be found at http://www.math.uga.edu/~azoff/courses/4690notes.pdf

    Review sessions were held scheduled 3 PM Friday and 7 PM Sunday in Room 410.  Practice problems in bold typeface could be used to help study for the final and could be brought up at the review sessions.

    Material from the above April schedule will be covered on the final; if your percentage score on the relevant final exam questions is higher than the average of your scores on the two hour tests,  that will percentage will be used as a third hour score in your course average.

    The second hour test was held Wednesday, April 2.  It covered through Chapter 5 of the text.  The median score (including up to 10 extra points for test corrections) was 76. You may find the comments and example at http://www.math.uga.edu/~azoff/courses/4690Exam2n.pdf helpful in understanding the grading of Problem 5 on the test.

    The first hour test was held on Friday, February 8.  It covered Chapters 1 and 2 of the text.  The median score was 74. 
    Solutions to the exam are posted at http://www.math.uga.edu/~azoff/courses/4690t1soln.pdf.

    The following study suggestions were given.
    Back to Contents


    MATH (CSCI) 4690 (6690) Spring 2008
    Graph Theory
    Course Syllabus

    Call Numbers 70-565 (MATH 4690)
    90-566 (MATH 6690)
    80-882 (CSCI 4690)
    00-883 (CSCI 6690)



    Web Page  http://www.math.uga.edu/~azoff/courses/4690.html 



    Time & Place 12:10 - 1:00 PM on MWF
    		 304 Boyd



    Text  Title:           Graph Theory: Modeling, Applications, and Algorithms
    Authors:      Geir Agnarsson and Raymond Greenlaw
    Publisher:    Pearson Education, Inc;  2007
    ISBN:         0-13-14284-3



    Prerequisites
    		 Linear Algebra (e.g., MATH 3000 or 3500)
    Logic, sets, relations, functions, induction (e.g. MATH 3200 or CSCI 2610)



    Topics Basic Material (Chapters 1 - 7)
    Selected supplements, depending on class interests
    		 10 weeks
      5 weeks 



    Grading Homework 
    Hour Tests (3 @ 100 pts) 
    Final Exam    		 100 points 
    300 points 
    200 points




    		Homework will be collected about once a week;  no late work will be accepted.
    CSCI/MATH 6690 students are expected to include at least one grad/bonus problem in each assignment.
    The final exam is scheduled for Noon - 3 PM on Monday May 5;  it will be comprehensive. 



    Instructor E. Azoff 
         e-mail 
         Phone 
         Office 
    		azoff@math.uga.edu
    542-2608 
    443 Boyd 

    Hours (Tentative)
    		 Monday through Friday:                     1:30 - 2:30 PM  No Office Hours on:
         Monday April 21

    First Assignment 
    Due Wednesday January 16

    Reading
    		 Problems
    Pages
    		 Hand In
    		 Grad/Bonus
    		 Class Discussion / Extra Practice
    Chapter 1
    		 26-30
    		 5,8,9*,10,12,14,16,21,22,24,26,32
    		 1,6,20,34
    		 2,3,4,9,11,13,15,17,19,25,33

    *Use Figure 1.15 rather than Figures 1.4 and 1.5.  You will need to assign names to the edges appearing in Figure 1.15.
    Practice problems should be looked over early, so troublesome concepts can be brought up for class discussion.

    Back to Contents