MATH 454 – Graph Theory and Applications
Course Description from Bulletin: Directed and undirected graphs; paths, cycles, trees,Eulerian cycles, matchings and coverings, connectivity, Menger’s Theorem,network flow, coloring, planarity, with applications to the sciences (computer, life, physical, social) and engineering. (3-0-3) (C)
Enrollment: Elective for AM and other majors
Textbook(s): West, Introduction to Graph Theory, 2nd ed., Prentice Hall
Other required material:
Prerequisites: (MATH 230 and MATH 251) OR (MATH 230 and MATH 252)
Objectives:
1. Students will achieve command of the fundamental definitions and concepts of graph theory.
2. Students will understand and apply the core theorems and algorithms, generating examples as needed, and asking the next natural question.
3. Students will achieve proficiency in writing proofs, including those using basic graph theory proof techniques such as bijections, minimal counterexamples, and loaded induction.
4. Students will work on clearly expressing mathematical arguments, in discussions and in their writing.
5. Students will become familiar with the major viewpoints and goals of graph theory: classification, extremality, optimization and sharpness, algorithms, and duality.
6. Students will be able to apply their knowledge of graph theory to problems in other areas, possibly demonstrated by a class project.
Lecture schedule: Three 50 minute (or two 75 minute) lectures per week
|
Course Outline:
|
Hours
|
1. Fundamental concepts of graphs
a. Basic definitions of graphs and multigraphs; adjacency matrices, isomorphism, girth, decompositions, independent sets and cliques, graph complements, vertex coloring, chromatic number, important graph like cubes and the Petersen graph
b. Paths, cycles, and trails; Eulerian circuits
c. Vertex degrees and counting; large bipartite subgraphs, the handshake lemma, Havel-Hakimi Theorem
d. Directed graphs: weak connectivity, connectivity, strong components
e. Induction and other fundamental proof techniques
|
8
|
2. Treesa.
a. Basics: equivalent characterizations of trees, forests
b. Spanning trees and 2-switches
c. Distance and centerd. Optimization: Kruskal’s Theorem and Dijkstra’s Theorem
d. Optimization: Kruskal’s Theorem and Dijkstra’s Theorem
|
6
|
|
3. Matching and covering
a. Bipartite matching, vertex cover, edge cover, independent set, M-alternating path, Hall’s Theorem, König-Egeváry Theorem, Gallai’s Theorem
|
6
|
|
4. Connectivity
a. Vertex cuts, separating sets, bonds; vertex and edge connectivity, block-cutpoint tree
b. Menger’s Theorem: undirected vertex and edge versions
|
4
|
|
5. Network flow
a. Ford-Fulkerson Labeling algorithm, flow integrality, Max-flow/Min-cut Theorem, proof of Menger's Theorem
|
2
|
|
6. Coloring
a. Chromatic number: lower bounds from clique number and maximum independent set, upper bounds from greedy coloring (& Welsh-Powell), Szekeres-Wilf, and Brooks' Theorem. Also k-critical graphs, cartesian product of graphs, and interval graphs.
b. k-Chromatic graphs: Mycielski's construction, Turán's Theorem
c. Edge coloring, line graphs, Vizing’s Theorem
|
6
|
|
7. Planarity
a. Embeddings, dual graphs, Euler's formula
b. Kuratowski's Theorem
c. Coloring, including the 5-color theorem
|
5
|
8. Student projects on applications of graph theory
|
1
|
Assessment:
Homework/Project
|
10-50%
|
Quizzes/Examss
|
20-50%
|
Final Exam
|
30-50%
|
Syllabus prepared by: Rob Ellis, Hemanshu Kaul, and Michael Pelsmajer
Date: 03/02/15 (updated from 03/06/06 and 01/26/12)