Graph Theory
mathematics
about this course
Graph Theory is a central area of discrete mathematics concerned with the study of
graphs, mathematical structures used to model pairwise relations between objects. This
course provides a rigorous introduction to the fundamental concepts, results, and methods of
graph theory, together with selected topics from algebraic graph theory and network
optimization.
The course begins with the basic definitions and properties of graphs, including paths, cycles,
trees, connectivity, and degree sequences. It then develops algorithmic techniques for
spanning trees, shortest paths, and related optimization problems. The second part introduces
algebraic tools for studying graphs, including adjacency and Laplacian matrices, eigenvalues,
eigenvectors, and their interpretations in terms of structure and centrality.
Building on this foundation, the course explores network flows, duality, and the Max-
Flow/Min-Cut theorem, along with applications to combinatorial optimization. The final
module addresses advanced topics such as graph coloring, random graphs, and some more
algebraic graph theory.
By the end of the course, students will have a clear understanding of the theoretical principles
underlying modern graph theory and will be able to apply mathematical reasoning to analyze
and solve problems involving discrete structures and networks.
in these programmes
- computer science
elective · 4-year major, 4-year double major, 3-year major, 3-year double major, 4-year minor, 3-year minor, concentration (4-year), concentration (3-year)
- mathematics
elective · 4-year major, 4-year double major, 3-year major, 3-year double major, 4-year minor, 3-year minor, concentration (4-year), concentration (3-year)
planning & teaching
before this
recently taught by
- Raghavan K NProfessor, Mathematics
Recorded in 2026 T2, 2025 T3. Instructors may change.