COURSE NUMBER AND TITLE: MATH 4420 Introduction to the Theory of Graphs

CREDIT HOURS: 3

CATALOG DESCRIPTION: A study of graphs, subgraphs, paths, arcs, trees, circuits, digraphs, colorability.

PREREQUISITE(S): MATH 2030 or CSCI 3030

SUGGESTED TEXT(S):
Introductory Graph theory by Gary Chartrand
Graphs and Digraphs by Chartrand and Lesniak
Graphs and their Uses by Oystein Ore

COURSE OUTLINE:

1. Basic concepts of graph theory
   • The definition of a graph and examples of applications using graphs
   • Isomorphic graphs
   • Paths and distance in graphs
   • Connected graphs, cut-vertices and cut-edges of a graph
   • Circuits and cycles
   • The Konigsberg bridge problem and Euler cycles
2. More advanced concepts of graph theory
   • Trees and spanning trees
   • Bipartite graphs
   • Planar graphs and Kuratowski's Theorem
   • Euler's formula
   • Graph colorings
3. Other topics
   • Hamiltonian graphs
   • Algorithms for finding Euler/Hamilton cycles
   • Kruskal's algorithm
   • Complexity of algorithms
   • Matching in graphs
   • Directed graphs and tournaments
   • Ramsey numbers/Ramsey theory
   • Algebraic methods in graph theory (adjacency matrices, eigenvalues of a graph, and applications