Graph Theory

Connectivity measures the resilience of a graph when vertices or edges are removed. Learners will understand paths, cycles, cut-sets, and Menger's theorem, enabling them to analyze the reliability and flow of network infrastructures like communication and transportation systems.

Extremal graph theory studies how global properties of a graph, such as its size or density, force the existence of specific local substructures. Learners will understand Turán's theorem, Ramsey numbers, and how to determine maximum or minimum graph parameters.

Graph coloring is the assignment of labels to elements of a graph subject to certain constraints. Learners will understand how to color vertices, edges, or faces to avoid conflicts and solve scheduling and resource allocation problems.

This topic covers the fundamental structures of undirected and directed graphs. Learners will understand how to model pairwise relationships, analyze network connectivity, and apply basic graph algorithms to solve routing and structural problems.

Matching theory explores how to select independent edges in a graph. Learners will understand how to solve assignment problems, analyze stable marriages, and apply algorithms like Hall's Marriage Theorem to resource allocation.

Network flows involve directing traffic through a network with capacity constraints. Learners will understand the Max-Flow Min-Cut theorem and apply algorithms to optimize transportation, logistics, and data routing problems.

Planar graphs are graphs that can be drawn on a plane without intersecting edges. Learners will understand Euler's formula, Kuratowski's theorem, and how to analyze map colorings and circuit board layouts.

Random graphs study probability distributions over graphs. Learners will understand how network properties emerge as edges are added randomly, allowing them to model real-world networks like social systems and the internet.

Spectral graph theory studies the properties of graphs in relation to the eigenvalues and eigenvectors of their associated matrices. Learners will understand how to analyze network structure, connectivity, and graph partitioning.

Trees are connected, acyclic undirected graphs. Learners will understand the structural properties of trees, spanning tree algorithms, and how to use these structures for hierarchical data representation and efficient searching.