Unit · year 3
MU-307 · Combinatorics & Graph Theory
Threads structure · number5 theorems
Extremal and structural results about finite configurations.
Theorems in this unit
T-109
Ramsey's theorem
Complete disorder is impossible in large enough structures.
T-110
Hall's marriage theorem
A matching exists iff every set of vertices has enough neighbours.
T-111
The max-flow min-cut theorem
Maximum flow equals minimum cut capacity.
T-112
Kuratowski's theorem
A graph is planar unless it contains K5 or K3,3.
T-113
Turán's theorem
The maximum edges in a graph with no large clique.