CS 570 Graph Theory Spring 2012
Instructor: Ugur Dogrusoz
Office, Hours: EA-429, Wed, Thu PM
Classroom, Hours: EB-204, Wed 13:40 & 14:40, Fri 15:40

  • HW 5 solutions are now available
  • Final solutions are now available
  • Unless otherwise stated, we do not hold the following lecture hour: Fri 16:40-17:30
  • Check here at least once a week!
Description Fundamentals of graph theory will be covered along with certain graph theory applications as review topics if time permits. Topics include paths and searching, trees, networks, cycles, planarity, matching, and independence.
Prerequisite Prior knowledge of fundamentals of computer science or graph theory required. Permission from the instructor required for undergraduates.
  • Become accomplished in formal / mathematical theorem proving using the fundamental techniques of construction, induction, and contradiction (as opposed to traditional/informal proof methods).
  • Learn the fundamentals of graph theory, which is an important mathematical tool in a wide variety of subjects from operational research and chemistry to genetics and linguistics, and from electrical engineering and geography to sociology, architecture, and computer science.
  • Become acquainted with the structure of graphs, and how to determine the relationship between graph invariants (such as order, size, or minimum degree) and a graph property (like being hamiltonian, containing a perfect matching).
  • Relate theory to practice through the study of certain graph theory applications.
Textbooks Required
  • Graph Theory by Reinhard Diestel, Springer, ISBN-13: 978-3642142789. electronic copy
  • Introduction to Graph Theory, 4th Edition by Robin J. Wilson, Logman Group Ltd., ISBN 0-582-24993-7.
  • Graph Theory by Ronald Gould, Benjamin-Cummings, QA166.G66 1988.
  • Graphs, Networks and Algorithms by Dieter Jungnickel, Springer, 1999, ISBN 3-540-63760-5.
  • Graph Theory Applications by L.R. Foulds, Springer-Verlag, 1991, ISBN 3-540-97599-3.
Outline &
Lecture Notes
Concepts Textbook
Foundations -
Basics Chapter 1
Matching Chapter 2
Connectivity Chapter 3
Planarity Chapter 4
Coloring Chapter 5
Flows Chapter 6
Hamilton Cycles Chapter 10
Grading Criteria:
Component Weight Date/Due
Attendance 05 -
Homework 60 -
Midterm 15 in-class (Apr 4, 2012, 13:00-15:30)
Final 20 in-class (May 2, 2012, 13:00-15:30)
Assignments & Exams
Homework Exams
HW 5 Solutions
HW 4 Solutions
HW 3 Solutions
HW 2 Solutions Final Solutions
HW 1 Solutions Midterm Solutions