Professor: Ron Gould

Text: Graph Theory by Ron Gould (Dover Publications) + additional materials provided.

 Office: 432 Mathematics and Science Center Office Hours: 10:30-11:30 WF - or by appointment Office Phone: 404-727-7924 email: rg@mathcs.emory.edu Some Important Graphs: Petersen Graph Tutte Graph Flower Snark Graph • Handouts on Embeddings on Surfaces and Max Genus
• Chapter Seven - Matchings and r-Factors
• Chapter Eight - Independence
• Chapter Ten - Extremal Theory

• Vizing's Theorem Proof [pdf]
• Read handout on graph embeddings by Jan. 24
• Read Handout on max genus by Jan . 31
• Read Chapter 7 by Friday, Feb. 21
• Read handout on factoring by Monday, Wednesday Feb. 26
• Read Chapter 8 by March 20
• Read Vizing's Theorem Proof by March 22
• Read handouts by March 26 Graph Theory Hall of Fame: (semester 2) Erdos Tutte Turan Ringel  Hall Konig Berge Petersen Written Assignments:

• Assignment 1: From handouts: Page 125: problems 33, 34, 35, 36 and Page 140, problem 41 and page 141: Problem 42

Also Problem: Find an embedding for the complete bipartite graphs:

(i) K(4,4) on the torus, (ii) K(4,5) on the double torus,

and for the complete graphs,

(iii) K(6) on the torus, (iv) K(8) on the double torus.

Page 151, problems 54, 55

• Assignment 2: Chapter 7 - problems 1, 2, 3, 4, 5, 12, 18, 19.
• from handout: pg 300-301, problems 33, 34, 35

• Assignment 3: Chapter 8 - problems 2, 3, 5, 7, 15, 18, 26d, 27.

(A) Show the Petersen graph has a nowhere zero 5-flow.

(B) Find the error in the "proof" of the 4CT given in handouts.

(C) From handouts: pg 235 problems 16, 17, pg 245 problem 27, pg 258 problem 37

(D) Find a cycle double cover for the Petersen graph.

• Assignment 4: Chapter 10 - problems 1, 2, 3, 14 and bonus problems (18, 19)

(i) Determine the extremal number for the star K_1,d.

(ii) Considering the results shown in class about the number of triangles

in a graph, show which result is best over the various subintervals of

values of q from (n^2)/10 up to its max value. A plot of the functions will suffice.

(iii). Determine which of the following functions is convex.

Consider the interval as ( 1, inf ).

a. f(x) = sqrt(x)

b. f(x) = x choose 2, (i.e. binomial coefficients)

c. f(x) = x ^ 2 (i.e. x squared)

d. f(x) = log x

(iv) Show that any epsilon-regular pair in G is also epsilon-regular

in the complement of G.

(v) In the definition of an epsilon-regular pair, what is the

purpose of the requirement that |X| > epsilon|A| and |Y| > epsilon|B|?  -->