MAT 485E - Introduction to Graph Theory

Course Objectives

1. To introduce graph theory.
2. To further knowledge of discrete mathematics.
3. To teach structural and external approaches.
4. To teach proof techniques and applications of discrete mathematics.
5. To teach basic algorithms and complexity.

Course Description

Graphs and directed graphs, paths, cycles, trails, degrees and counting. Trees and their basic properties. Spanning trees and enumeration. Matchings and covers, matchings in general graphs. Cuts and paths: Connectivity, cuts and connectivity, k- connected graphs, network flow. Coloring: Vertex coloring and upper bounds, structure of k-chromatic graphs. Selected algorithms and applications.