The course consists of two parts. Part A is dedicated to Graph Theory.
Part B is held by Prof. Giovanna Citti Ph.D.
Theory
1. Graphs and subgraphs (1.1 to 1.8).
Theorems: Thm. 1.1 (with proof), Cor. 1.1 (with proof), Thm.1.2 (with proof)
2. Trees (2.1; 2.2 up to Cor. 2.4.2; 2.3 to 2.5).
Theorems: Thm. 2.1 (with proof), Thm.2.2 (with proof), Cor. 2.2, Thm. 2.3,
Thm. 2.4, Cor. 2.4.1, Cor. 2.4.2 (with proof), Thm. 2.7, Thm. 2.8 (with proof),
Thm. 2.9.
3. Connectivity (3.1; 3.2 up to Cor. 3.2.2).
Theorems: Thm. 3.1, Thm. 3.2, Cor. 3.2.1, Cor. 3.2.2
4. Euler tours and Hamilton cycles (4.1; 4.2 up to Cor. 4.4; 4.3 up to Fleury'alg.;
4.4: first 10 lines).
Theorems: Thm. 4.1, Cor. 4.1, Thm. 4.2, Thm. 4.3 (with proof), Thm. 4.4, Cor. 4.4.
5. Matchings (5.1, 5.2; 5.4: first 8 lines).
Theorems: Thm. 5.1, Thm. 5.2, Cor. 5.2, Lemma 5.3, Thm. 5.3.
6. Edge colourings (6.1: first 20 lines, Thm. 6.1; 6.2: Thm. 6.2; 6.3: first 21 lines).
Theorems: Thm. 6.1, Thm. 6.2.
7. Independent sets and cliques (7.1; 7.2 up to Thm. 7.4).
Theorems: Thm. 7.1 (with proof), Cor. 7.1 (with proof), Thm. 7.2, Thm. 7.3, Thm. 7.4.
8. Vertex colourings (8.1 up to Cor. 8.1.2; 8.2; 8.3: only Thm. 8.5; 8.4; 8.5: only Thm. 8.7; 8.6).
Theorems: Thm. 8.1 (with proof), Cor. 8.1.1 (with proof), Cor. 8.1.2 (with proof), Thm. 8.4, Thm. 8.5,
Thm. 8.6 (with proof), Cor. 8.6, Thm. 8.7.
9. Planar graphs (9.1 excluding Thm. 9.1; 9.2; 9.3; 9.5 without lemmas and without proof; 9.6 up to Thm. 9.12 excluded, without proof; mind the footnotes!).
Theorems: Thm. 9.2 (with proof), Thm. 9.3 (with proof), Thm. 9.4 (with proof), Thm. 9.5 (with proof), Cor. 9.5.1 (with proof), Cor. 9.5.2 (with proof), Cor. 9.5.3 (with proof), Cor. 9.5.4 (with proof), Cor. 9.5.5 (with proof), Thm. 9.10, Thm. 9.11, footnote at p. 157.
10. Directed graphs (10.1; 10.2 up to Cor. 10.1; 10.4 first 17 lines; 10.5; 10.6 up to Thm. 10.5).
Theorems: Thm. 10.1 (with proof), Cor. 10.1 (with proof), Thm. 10.5 (with proof).
11. Networks (11.1; 11.2; 11.3).
Theorems: Thm. 11.1, Cor. 11.1, Thm. 11.2, Thm. 11.3.
12. The cycle space and bond space (12.1)
Theorems: Thm. 12.1, Lemmas 12.2.1, 12.2.2, Thm. 12.2, Cor. 12.2.
Exercises
Modelling problems with graphs. Writing matrices associated with graphs. Computing
graph invariants. Solving elementary graph problems: Shortest path problem (by Dijkstra's Algorithm),
Connector problem (by Kruskal's algorithm), Chinese postman problem (by Fleury's algorithm),
finding minimal coverings and maximal independent sets (by logical operations), making
a 2-edge-connected graph diconnected.
Building a maximal flow in a network.
