General
Welcome to Math 154. You will find course materials, announcements, and any lecture notes (see below) on this site.
There is no required book for this course. Additional reading includes the books displayed alongside.
Your grade comprises 20% Homework, 30% Midterm and 50% Final. It is your responsibility to be aware of the parameters of academic integrity and student conduct. Any suspected cases are reported to the academic integrity office.
The grading scheme for this course is as follows:
A+ 90-100, A 85-89.9, A- 80-84.9, B-/B/B+ 70-79.9, C-/C/C+ 60-69.9, F <50
Syllabus
Syllabus
Introduction to graph theory
Paths, trees and cycles, connected graphs, Eulerian graphs, Hamiltonian graphs, spanning trees. Disjktra's algorithm and Prim's algorithm.
Structure of connected graphs and matchings
Connectivity in graphs, Menger's Theorems, Hall's Theorem, Tutte's 1-Factor Theorem, stable matching, matching algorithms.
Graph coloring and planar graphs
Vertex and edge-coloring, Brooks' Theorem, Vizing's Theorem, planar graphs, Euler's Formula
Max Flow Min Cut Theorem
Flows, cuts and capacities,
max-flow-min-cut theorem and algorithm, Hall's and Menger's Theorems.
Additional Reading