The course consists of two parts. Part A is dedicated to Graph Theory.
Part B is held by Prof. Simonetta Abenda Ph.D. The following program will be updated during the course.

Theory

1. Graphs and subgraphs (1.1 to 1.7; 1.8 up to first 24 lines of page 19). Theorems: Thm. 1.1 (with proof), Cor. 1.1 (with proof), Thm.1.2 (with proof) Exercises: 1.1.3, 1.2.1, 1.2.3, 1.2.4, 1.2.10, 1.2.12(c), 1.3.1, 1.4.4, 1.5.1, 1.5.4, 1.5.5, 1.5.6(a), 1.6.1, 1.6.2, 1.6.3, 1.6.11, 1.7.2, 1.8.4.
2. Trees (2.1; 2.2 up to Cor. 2.4.2; 2.3 up to Thm. 2.7; 2.4; 2.5 up to Thm. 2.10 excluded). 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. Exercises: 2.1.4, 2.4.3.
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 Thm. 4.7; 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, Thm. 4.7. Exercises: 4.1.1, 4.1.2.
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. Exercises: 5.1.1(a), 5.1.2, 5.1.5(b).
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 the table of numbers). 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 up to 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. Exercises: 8.4.1, 8.4.2, 8.6.2.
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. Exercises: 9.1.2.
10. Directed graphs (10.1; 10.2 up to Cor. 10.1;
10.6 up to Thm. 10.5). Theorems: Thm. 10.1 (with proof), Cor. 10.1 (with proof), Thm. 10.5 (with proof). Exercises: 10.1.1

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.
The student is bound to (try to) solve the book exercises listed above for each chapter.

A mid-term test will be given in December, at a date which will be communicated in class and here.
The mid-term test MUST be passed with a score of at least 14 (over 24). If you don't pass, you must recover it; the dates for recovering coincide with the dates of the
written exams of the freshmen (see Prossimi appelli - Geometria e Algebra t (prova scritta). For doing so you have to communicate to me WHEN you want to take it before the final exam.

Apply for the final exam at AlmaEsami. The final exam is as follows: I propose two subjects; you choose one and write down all what you remember about it, and then we discuss on your essay and in general about the chosen subject.