Math 3332: Introduction to Graph Theory

Course description: Graph theory has been applied to many fields including other branches in mathematics, chemistry, biology and so on. With the current intensive interests in network systems, graph theory becomes even more popular. This course introduces some major topics in graph theory. More specifically, it discusses degrees, isomorphic graph, trees, connectivity, traversability, coloring graphs. If time allows, we will also discuss digraph, matching and factorization.

Prerequisites: MATH 3331 is the prerequisite for this class.
You are expected to understand the basic proof techniques covered in the prerequisite course and to be able to apply them.

Textbook: A First Course in Graph Theory, by Gary Chartrand and Ping Zhang

Course Content:

1. Introduction
   • Graph and Graph Model
   • Connected Graphs
   • Common Classes of Graphs
   • Multigraphs and Digraphs
2. Degrees
   • The degree of a vertex
   • Regular graphs
   • Degree sequences
3. Isomorphic Graphs
   • The definition of isomorphism
   • Isomorphism as a relation
4. Trees
   • Bridges
   • Trees
   • The minimum spanning tree problem
5. Connectivity
   • Cut vertices
   • Blocks
   • Connectivity
   • Menger’s Theorem
6. Traversability
   • Eulerian graphs
   • Hamiltonian graphs
   • Exploration: Hamiltonian walks
7. Planarity
   • Planar graphs
   • Embedding graphs on surface
8. Coloring Graphs
   • The four color problem
   • Vertex Coloring
   • Edge Coloring