Graph Theory I - Math 531 - Fall 2011

the claw Konigberg Bridges

Text: Graph Theory by Ron Gould (see below), plus additional materials.

Office: E432 Math & Science Center	Office Hours: 11:00-12:00 MWF or by appointment
Office Phone: 404-727-7924	email: rg@mathcs.emory.edu
web page http://www.mathcs.emory.edu/~rg/m531.html

Materials: Copyright 2001 - Ronald J. Gould

• Table of Contents [ps] [pdf]
  
• Chapter One - Graphs [ps] [pdf]
  
• Chapter Two - Paths and Searching [ps] [pdf]
  
• Chapter Three - Trees [ps] [pdf]
  
• Chapter Four - Networks [ps] [pdf]
  
• Chapter Five - Cycles and Circuits [ps] [pdf]
  
• Chapter Six - Planarity [ps] [pdf]
  
• Index [ps] [pdf]
  

Euler Hamilton Kuratowski Ore

Reading Assignments:

Chapter 6

Written Assignments:

• Assignment 1: Chapter 1 - problems 4, 14, 16, 19, 21, 29, 30, 37, 38, 45
  
  
• Assignment 2: Chapter 2 - problems 7, 8, 11, 12, 28, 29 and the following problems:
  1. Prove that a graph G is 2-connected if and only if for every triple of distinct vertices (x,y,z), G has an x-z path through y.
  
  2. Prove that a graph G of order at least four is 2-connected if and only if for every pair X and Y of disjoint vertex subsets with |X| and |Y| at least 2, there exists two completely disjoint paths R and S
  in G such that each has an endvertex in X and an endvertex in Y and no internal vertex in X or Y.
  
  3. Determine all graphs for which every orientation is unilateral.
  
  4. Prove or disprove: If every orientation of a graph G of order at least 5 is anticonnected, then the minimum degree of G is at least 4.
  
  
• Assignment 3: Chapter 3 - problems 6, 11, 20, 23, Bonus Problems 24, 25 and Chapter 4 - Problems 2, 5, 8, 9, 17 and
  
  1. Show that all caterpillars are graceful.
  2. Prove that if T_i is a path on i vertices, then T_1, T_2, ... , T_n can be packed into K_n.
  
  
• Assignment 4: Chapter 5 - problems 8, 10, 12, 13, 15, 16, 17, 25, 35, 40, 54
  
  
  
• Assignment 5: Chapter 6 - problems 1, 5, 8, 9, 10, 11, 21, 22
  In addition, the following problems:
  
  1. Prove that every 3-connected graph with at least six vertices that contains a subdivision of K_5 also contains a subdivision of K_{3,3}.
  
  2. Let H be a graph with maximum degree at most 3. Prove that a graph G contains a subdivision of H if and only if G contains a graph contractable to H.
  Note: Problems due December 9.