# Graph Theory I - Math 531 - Fall 2011

## Professor: Ron Gould

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

This is copyright material and is intended for use by students in Math 531 only or with the permission of the author.

Graph Theory Hall of Fame: (1st semester)
Euler Hamilton Kuratowski Ore

• Chapter 1
• Chapter 2 and handouts
• Chapter 3 and handouts
• Chapter 4
• Chapter 5 and handouts
• 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