本科高年级Discrete Mathematics计划中

Graph theory

Connectivity, matchings and Hall's theorem, colouring, planarity and Euler's formula, extremal results such as Turán's theorem, and Ramsey theory.

math.discrete.graph-theory

本主题的课程尚未编写。下面的提纲是课程地图的一部分，尚未经过审校。

前置知识

18 项必需的前置知识（一直追溯到底）

Prove Hall's marriage theorem and apply it.
Prove Euler's formula V − E + F = 2 for connected plane graphs and deduce that K₅ and K₃,₃ are not planar.
Prove that R(3, 3) = 6 and establish upper bounds for Ramsey numbers.

A matching is a set of edges no two of which share a vertex.
A proper k-colouring assigns one of k colours to each vertex so that adjacent vertices receive different colours.
The Ramsey number R(s, t) is the least n such that every red–blue colouring of the edges of Kₙ contains a red K_s or a blue K_t.

Hall: a bipartite graph with parts A and B has a matching covering A if and only if |N(S)| ≥ |S| for every S ⊆ A.
Four colour theorem (Appel and Haken, 1976): every planar graph is 4-colourable; the proof relies on computer verification.
Kuratowski: a graph is planar if and only if it contains no subdivision of K₅ or K₃,₃.
R(3, 3) = 6.

Thinking a graph is planar only if a given drawing has no crossings; it is planar if some drawing has none.
Assuming the four colour theorem has a short proof checkable by hand; known proofs use computers, and one has been formally verified in Coq.

Computational complexity Deciding whether a graph is 3-colourable is NP-complete.
← Algorithm design and analysis