About the course
The adjacency matrix and walks, the complement and isomorphism, distances and diameter. Bridges, trees, the Prüfer code and Cayley's formula, counting spanning trees. Euler trails and the postman problem, Dirac's and Ore's conditions, the hypercube and the Gray code. Bipartite graphs, the theorems of König and Hall, stable matchings. Vertex and edge coloring, the chromatic polynomial. Euler's formula, bounds on the number of edges, Kuratowski's theorem. The Bellman–Ford and Floyd–Warshall algorithms, flows and Menger's theorem, the theorems of Mantel and Ramsey. A continuation of discrete mathematics.
Course program: 33 lessons
Graphs, matrices, distances
- Adjacency matrix and walks
- Complement and isomorphism
- Distances, diameter, radius
- Checkpoint: matrices, isomorphism, distances
Connectivity and trees
- Bridges and cut vertices
- Trees and forests
- Prüfer code and Cayley's formula
- The number of spanning trees
- Checkpoint: connectivity and trees
Euler and Hamilton
- Euler trails and the postman
- Hamilton cycles: Dirac and Ore
- Hypercube and Gray code
- Checkpoint: Euler and Hamilton
Bipartite graphs and matchings
- Bipartite graphs
- Matchings and vertex covers
- Hall's theorem and deficiency
- Stable matchings
- Checkpoint: bipartite graphs and matchings
Coloring
- Chromatic number and bounds
- Chromatic polynomial
- Edge coloring
- Checkpoint: coloring
Planarity
- Euler's formula for plane graphs
- Edge bounds for planar graphs
- Kuratowski's theorem
- Checkpoint: planarity
Paths, flows, extremal problems
- The Bellman–Ford algorithm
- The Floyd–Warshall algorithm
- Flows: augmenting paths
- Menger's theorem and connectivity
- Mantel's and Ramsey's theorems
- Checkpoint: paths, flows, extremal problems
Final test
- Final test in graph theory