Graph Theory

Catalog description

This course introduces students to the field of graph theory and leads them through an exploration of the major branches of this subject, incorporating both theoretical results and current applications for each area studied. From a theoretical perspective, students re-derive well-known existing results and construct proofs related to new topics which have been introduced. From an applied standpoint, members of the class learn to formulate graph models to solve problems in computer science, the natural sciences, engineering, psychology, sociology, and other fields. We also consider some open problems and pose new questions of our own. In addition to fundamental definitions and concepts in graph theory, some specific topics that will be introduced are the following: Eulerian, Hamiltonian, planar, and directed graphs; trees, connectivity, matching, decomposition, coloring, covering, and independent sets and cliques; techniques and algorithms on graphs; and optimization problems and network flows.