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