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

**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]

Graph Theory Hall of Fame: (1st semester)

- 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.