Graph Theory

mathematics

credits
4
recorded trimesters
T2, T3
open to
year 3, 4
last offered
2026 T2

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 programmes2026 batch
  • 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 this1
recently taught by1

Recorded in 2026 T2, 2025 T3. Instructors may change.

Course data from Krea's term sheets (July 2026); programme rules from the departments' FYUP documents. Check anything that matters with your department.