MA 320 - Graph Theory

1. Introduction
   a) What is a Graph?
   b) The Degree of a Vertex
   c) Isomorphic Graphs
   d) Subgraphs
   e) Degree Sequences
   f) Connected Graphs
   g) Cut-Vertices and Bridges
   h) Special Graphs
   i) Digraphs
   
   
2. Trees
   a) Properties of Trees
   b) Rooted Trees
   c) Depth-First Search Algorithm
   d) Beadth-First Search Algorithm
   e) The Minimum Spanning Tree Problem
   
   
3. Paths and Distances in Graphs
   a) Distance in Graphs
   b) Distance in Weighted Graphs
   c) The Center and Median of a Graph
   
   
4. Eulerian Graphs
   a) Characterizing Eulerian Graphs
   b) The Chinese Postman Problem
   
   
5. Hamiltonian Graphs
   a) Characterizing Hamiltonian Graphs
   b) The Traveling Salesman Problem
   
   
6. Planar Graphs
   a) Properties of Planar Graphs
   b) A Planarity-Testing Algorithm
   c) The Crossing Number and Thickness of a Graph
   
   
7. Coloring Graphs
   a) Vertex Colorings
   b) Edge Colorings
   c) The Four Color Problem
   
   
8. Additional Topics depending on time and student interest
   a) Networks
   b) Matchings and Factorizations
   c) Digraphs
   d) Extremal Graph Theory
   e) Going Deeper into Topics 1 - 7

Learning Outcome 1: The student will understand and be able to apply the basic definitions of graph theory.

Learning Outcome 2: The student will understand the concepts of connectivity, distances, and traversability.

Learning Outcome 3: The student will understand the concepts of planarity and coloring.