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

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.

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 on the whole program above and is as follows: I propose two subjects (each of which is either the title of a long chapter, or the sum of the titles of two short ones); 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. It is an oral examination, so writing is only a help for you to gather ideas.