"Introduction to Graph Theory" Webpage

Introduction to Graph Theory - Class Notes
From Pearls in Graph Theory: A Comprehensive Introduction, by Nora Hartsfield and Gerhard Ringel, (San Diego: Academic Press, 1994) Hartsfield and Ringel's Pearls in Graph Theory book

Hartsfield and Ringel's Pearls in Graph Theory book

Hartsfield and Ringel's Pearls in Graph Theory book, Dover Publications reprint

The 1994 Academic Press version and the 2003 Dover Publications reprint of Pearls in Graph Theory

The catalog description for Introduction to Graph Theory (MATH 4347/5347) is: "Covers topics that include graph theory and applications, trees, planar graphs, graphical invariants, and networks." The prerequisite is Mathematical Reasoning (MATH 3000). ETSU also has a graduate-only sequence in graph theory consisting of Graph Theory 1 (MATH 5340) and Graph Theory 2 (MATH 5450; follow these links for notes used in those classes). In addition, there is Mathematical Modeling Using Graph Theory (MATH 5870), a class that was originally part of the online certificate program in Mathematical Modeling in Biosciences Graduate Certificate (however, this certificate program is no longer offered).

Copies of the classnotes are on the internet in PDF format as given below. The notes and supplements may contain hyperlinks to posted webpages; the links appear in red fonts. The "Proofs of Theorems" files were prepared in Beamer. The "Printout of Proofs" are printable PDF files of the Beamer slides without the pauses. These notes have not been classroom tested and may have typographical errors.

Chapter 1. Basic Graph Theory.
Chapter 2. Colorings of Graphs.
Chapter 3. Circuits and Cycles.
Chapter 4. Extremal Problems.
Chapter 5. Counting.
Chapter 6. Labeling Graphs.
Chapter 7. Applications and Algorithms.
Chapter 8. Drawings of Graphs.
Chapter 9. Measurements of Closeness to Planarity.
Chapter 10. Graphs on Surfaces.

1. Basic Graph Theory.

1.1. Graphs and Degrees of Vertices. Section 1.1 notes

Supplement. Proofs from Section 1.1. Beamer file of Section 1.1 proofs (prepared in Beamer).
Supplement. Printouts of Proofs from Section 1.1. Print file of Section 1.1 proofs

1.2. Subgraphs, Isomorphic Graphs. Section 1.2 notes

1.3. Trees. Section 1.3 notes

Supplement. Proofs from Section 1.3. Beamer file of Section 1.3 proofs (prepared in Beamer).
Supplement. Printouts of Proofs from Section 1.3. Print file of Section 1.3 proofs

Study Guide 1

2. Colorings of Graphs.

2.1. Vertex Colorings. Section 2.1 notes

Supplement. Proofs from Section 2.1. Beamer file of Section 2.1 proofs (prepared in Beamer).
Supplement. Printouts of Proofs from Section 2.1. Print file of Section 2.1 proofs

2.2. Edge Colorings. Section 2.2 notes

Supplement. Proofs from Section 2.2. Beamer file of Section 2.2 proofs (prepared in Beamer).
Supplement. Printouts of Proofs from Section 2.2. Print file of Section 2.2 proofs

2.3. Decompositions and Hamilton Cycles. Section 2.3 notes

Supplement. Proofs from Section 2.3. Beamer file of Section 2.3 proofs (prepared in Beamer).
Supplement. Printouts of Proofs from Section 2.3. Print file of Section 2.3 proofs

2.4. More Decompositions. Section 2.4 notes

Supplement. Proofs from Section 2.4. Beamer file of Section 2.4 proofs (prepared in Beamer).
Supplement. Printouts of Proofs from Section 2.4. Print file of Section 2.4 proofs

Study Guide 2

3. Circuits and Cycles.

3.1. Eulerian Circuits. Section 3.1 notes

Supplement. Proofs from Section 3.1. Beamer file of Section 3.1 proofs (prepared in Beamer).
Supplement. Printouts of Proofs from Section 3.1. Print file of Section 3.1 proofs

3.2. The Oberwolfach Problem. Section 3.2 notes

Supplement. Proofs from Section 3.2. Beamer file of Section 3.2 proofs (prepared in Beamer).
Supplement. Printouts of Proofs from Section 3.2. Print file of Section 3.2 proofs

3.3. Infinite Lattice Graphs. Section 3.3 notes

Study Guide 3

4. Extremal Problems.

4.1. A Theorem of Turan. Section 4.1 notes

Supplement. Proofs from Section 4.1. Beamer file of Section 4.1 proofs (prepared in Beamer).
Supplement. Printouts of Proofs from Section 4.1. Print file of Section 4.1 proofs

4.2. Cages. Section 4.2 notes

Supplement. Proofs from Section 4.2. Beamer file of Section 4.2 proofs (prepared in Beamer).
Supplement. Printouts of Proofs from Section 4.2. Print file of Section 4.2 proofs

4.3. Ramsey Theory. Section 4.3 notes

Supplement. Proofs from Section 4.3. Beamer file of Section 4.3 proofs (prepared in Beamer).
Supplement. Printouts of Proofs from Section 4.3. Print file of Section 4.3 proofs

Study Guide 4

5. Counting.

5.1. Counting 1-Factors. Section 5.1 notes

Supplement. Proofs from Section 5.1. Beamer file of Section 5.1 proofs (prepared in Beamer).
Supplement. Printouts of Proofs from Section 5.1. Print file of Section 5.1 proofs

5.2. Cayley's Spanning Tree Formula. Section 5.2 notes

Supplement. Proofs from Section 5.2. Beamer file of Section 5.2 proofs (prepared in Beamer).
Supplement. Printouts of Proofs from Section 5.2. Print file of Section 5.2 proofs

5.3. More Spanning Trees. Section 5.3 notes

Supplement. Proofs from Section 5.3. Beamer file of Section 5.3 proofs (prepared in Beamer).
Supplement. Printouts of Proofs from Section 5.3. Print file of Section 5.3 proofs

Study Guide 5

6. Labeling Graphs.

6.1. Magic Graphs and Graceful Trees. Section 6.1 notes

Supplement. Proofs from Section 6.1. Beamer file of Section 6.1 proofs (prepared in Beamer).
Supplement. Printouts of Proofs from Section 6.1. Print file of Section 6.1 proofs

6.2. Conservative Graphs. Section 6.2 notes

Supplement. Proofs from Section 6.2. Beamer file of Section 6.2 proofs (prepared in Beamer).
Supplement. Printouts of Proofs from Section 6.2. Print file of Section 6.2 proofs

Study Guide 6

7. Applications and Algorithms.

7.1. Spanning Tree Algorithms.

7.2. Matchings in Graphs, Scheduling Problems.

7.3. Binary Trees and Prefic Codes.

8. Drawings of Graphs.

8.1. Planar Graphs. Section 8.1 notes

Supplement. Proofs from Section 8.1. Beamer file of Section 8.1 proofs (prepared in Beamer).
Supplement. Printouts of Proofs from Section 8.1. Print file of Section 8.1 proofs

8.2. The Four Color Theorem. Section 8.2 notes

Supplement. Proofs from Section 8.2. Beamer file of Section 8.2 proofs (prepared in Beamer).
Supplement. Printouts of Proofs from Section 8.2. Print file of Section 8.2 proofs

8.3. The Five Color Theorem. Section 8.3 notes

Supplement. Proofs from Section 8.3. Beamer file of Section 8.3 proofs (prepared in Beamer).
Supplement. Printouts of Proofs from Section 8.3. Print file of Section 8.3 proofs

8.4. Graphs and Geometry.

9. Measurements of Closeness to Planarity.

9.1. Crossing Number. Section 9.1 notes

Supplement. Proofs from Section 9.1. Beamer file of Section 9.1 proofs (prepared in Beamer).
Supplement. Printouts of Proofs from Section 9.1. Print file of Section 9.1 proofs

9.2. Thickness and Splitting Number.

9.3. Heawood's Empire Problem.

10. Graphs on Surfaces.

10.1. Rotations of Graphs. Section 10.1 notes

Supplement. Proofs from Section 10.1. Beamer file of Section 10.1 proofs (prepared in Beamer).
Supplement. Printouts of Proofs from Section 10.1. Print file of Section 10.1 proofs

10.2. Planar Graphs Revisited. Section 10.2 notes

Supplement. Proofs from Section 10.2. Beamer file of Section 10.2 proofs (prepared in Beamer).
Supplement. Printouts of Proofs from Section 10.2. Print file of Section 10.2 proofs

10.3. The Genus of a Graph. Section 10.3 notes

Supplement. Proofs from Section 10.3. Beamer file of Section 10.3 proofs (prepared in Beamer).
Supplement. Printouts of Proofs from Section 10.3. Print file of Section 10.3 proofs

Return to Bob Gardner's home page