Teoria dei Grafi
Academic Year 2025/2026 - Teacher: ELENA MARIA GUARDOExpected Learning Outcomes
The course has the following objectives:
Knowledge and understanding:
- Mathematic Instruments in graph theory such as theorems and algoritms will be provide in the course. They permit to develop mathematical abilities in reasoning and calculation. These abilities could permit to resolve known problems by mathematical model.
Applying and knowledge and understanding:
- At the end of course student will be able to get knowledge for a tightened use of new mathematical techniques and an understanding of treated arguments in such way to link them each other.
Making judgements:
- Course is based on logical-deductive method which wants to give to students authonomus judgement useful to understanding incorrect method of demonstration also, by logical reasoning, student will be able to face not difficult problems in graph theory with teacher's help.
Communication skills:
- In the final exam, student must show for learned different mathematical techniques an adapt maturity on oral communication using also multimedia tools.
Learning skills
- Autonomously student will be able to face application and theoretical arguments which could be studied in new classes or in different working fields; for example flow theory and connectivity have huge application on telecommunications field (Local Area Network and Metropolitan Area Network: LAN e MAN), on electrical and communication fields (Industrial design).
Course Structure
Graph Theory 9 CFU
teaching organization
total study 225 hours
152 hours of individual study
49 hours of frontal lectures
24 hours of exercises
The lessons will be held through classroom. In these lessons the program will be divided into the following sections: basic notions, planar graphs, cycles and cocycles, different graph connections, graph fluxes, matchings and coverings, colorability.
In each of these sections first it will be discussed the main theoretical topics and then showed how these topics can be linked to possible applications. Then algorithms can be presented, and they allow in many cases to identify particular graphs or solutions proposed by the theoretical results
Should teaching be carried out in mixed mode or remotely, it may be necessary to introduce changes with respect to previous statements, in line with the programme planned and outlined in the syllabus.
Learning assessment may also be carried out on line, should the conditions require it.
Information for students with disabilities and / or SLD
To guarantee equal opportunities and in compliance with the laws in force, interested students can ask for a personal interview in order to plan any compensatory and / or dispensatory measures, based on the didactic objectives and specific needs. It is also possible to contact the referent teacher CInAP (Center for Active and Participated Integration - Services for Disabilities and / or SLD) of our Department, prof.ssa Daniele.
Required Prerequisites
Attendance of Lessons
Detailed Course Content
Graphs: historical introduction, basic definitions
(degree, path, connectedness, etc.), theorem on vertex degrees, connected graphs, bipartite graphs, complete graphs.
Eulerian and Hamiltonian graphs: the problem of the Königsberg bridges, characterization of Eulerian graphs, the dodecahedron problem, and the (open) problem of characterizing Hamiltonian graphs.
Trees: definitions, characterization theorems, economic trees, minimum spanning trees (MST) and applications.
Planar graphs:
definitions and first theorems, Euler’s theorem, maximal planar graphs, non-planarity of K₅ and K₃,₃, Kuratowski’s theorem (statement only).
Factorizations:
matchings in a graph, perfect matchings, factorizations, factorization of complete and complete bipartite graphs, Hall’s theorem and its applications (e.g., transversals, Latin squares, (0,1)-matrices).
Vertex coloring:
vertex coloring of a graph, chromatic number, stability number, Brooks’ theorem, relations between the chromatic number and the stability number, relations between the chromatic number of a graph and that of its complement, Finck’s theorem (without proof).
Coloring of planar graphs, five-color theorem, four-color theorem (statement only), connection and contraction algorithm, Mycielski construction, chromatic density.
Edge coloring:
edge coloring of a graph, chromatic index, König’s theorem, Vizing’s theorem, the (open) problem of graph classification, the Petersen graph, generalized Petersen graphs (statements only).
Chromatic polynomial:
definitions, properties, and theorems; determination of the chromatic polynomial; characterization of trees through the chromatic polynomial; chromatic polynomial of cycles.
Applications of the chromatic polynomial: conditional arrangements, arrangements and vertex colorings, Sudoku and chromatic polynomials.
Internal and external stability:
definitions and theorems, internal stability number and external stability number, the eight queens problem (Gauss), the problem of the minimum number of queens.
Directed graphs. Flow networks.
Ford–Fulkerson algorithm, strongly connected and minimally connected graphs, Tremaux algorithm, shortest path problem, cycles and cocycles, trees and cotrees: cyclomatic and cocyclomatic numbers, and recalls from linear algebra; trees and cotrees and their properties.
Applications of directed graphs (e.g., Markov chains, matroids).
Matroids: main concepts and definitions.
Should teaching be carried out in mixed mode or remotely, it may be necessary to introduce changes with respect to previous statements, in line with the programme planned and outlined in the syllabus.
Learning assessment may also be carried out on line, should the conditions require it.
“Contribution to Sustainable Development Goals 2030
Goal 4 Quality Education – Ensure inclusive and equitable quality education and promote lifelong learning opportunities.
Goal 5 Gender Equality – Achieve gender equality and empower all women and girls.
Goal 8: Decent Work and Economic Growth – Promote sustained, inclusive, and sustainable economic growth, full and productive employment, and decent work for all.
Graph theory helps to understand, optimize, and make economic and labor systems fairer. It fosters innovation, inclusion, and sustainability — the three fundamental pillars of Goal 8. It is a mathematical and computational tool with significant social and political implications.
Goal 11: Sustainable Cities and Communities – Make cities and human settlements inclusive, safe, resilient, and sustainable.
Goal 11 of the 2030 Agenda — “Sustainable Cities and Communities” — has a deep connection with graph theory, since cities are, in practice, complex networks of connections: roads, transportation systems, energy grids, and informational, social, and environmental flows. Practical examples of connections with the Goals:
-
Analysis of business networks to identify opportunities for local growth.
-
Study of scientific collaboration networks to develop high-innovation sectors.
-
Optimization of transportation and distribution networks to reduce waste and create jobs.
-
Modeling of the labor market to make employment more efficient and accessible.
Textbook Information
- C. Berge, "Graph and Hypergraph", Elsevier.
- Notes of the course - E. Guardo
- M. Gionfriddo, Notes on Graph Theory 2018 (available on Studium with the permission of Prof. Hemeritus M. Gionfriddo)
- R. J. Wilson, Introduction to Graph Theory
Course Planning
| Subjects | Text References | |
|---|---|---|
| 1 | graphs | 1),2),3) |
| 2 | Trees and their properties | 2) 3) 4) |
| 3 | Eulerian and Hamiltonian Graphs | 2) 3) 4) |
| 4 | Planar Graphs | 2) 3) |
| 5 | Factorizations, Matchings | 2) 3) |
| 6 | Vertex coloring | 1) |
| 7 | Edge coloring | 1) |
| 8 | Chromatic polynomial | 1) 2) 3) 4) |
| 9 | internal and external stability | 2) 3) |
| 10 | Digraphs | 1) 2) 3) |
| 11 | Flow network | 1) 2) |
| 12 | Strongly connected graphs | 3)4) |
| 13 | Matroids | 4) |
| 14 | Basic notion on G designs and hypergraphs | 1) 3) |
Learning Assessment
Learning Assessment Procedures
To take part in the final exam, it is necessary to register through the SmartEdu portal. For any technical issues related to registration, students must contact the Teaching Office.
a) Assessment during the course:
Periodically, during the lectures, students will be asked to recall definitions and results covered in previous lessons, in order to promote a conscious and active understanding of the subject.
b) Final exam:
The final exam consists of an oral test at the end of the course. The oral exam is particularly aimed at assessing the student’s clarity of expression and ability to connect different topics within the program.
d) Grading criteria:
The following aspects will be taken into account: clarity of exposition, completeness of knowledge, and ability to connect different topics.
The final grade will normally be assigned according to the following criteria:
-
Fail: the student has not acquired the basic concepts and is unable to solve exercises.
-
18–23: the student demonstrates a minimal command of the basic concepts; exposition and ability to connect topics are modest; able to propose only simple examples.
-
24–27: the student shows a good understanding of the course content; exposition and ability to connect topics are good.
-
28–30 cum laude: the student has mastered all course content, can present it thoroughly and critically connect topics; make exercisess.
NOTE:
The assessment of learning may also be conducted online, should circumstances require it.
Examples of frequently asked questions and / or exercises
Trees, Minimum Spanning trees
Eulerian and hamoltonian graphs
Planar graph and their property. Euler's formula.
Maximum and perfect matchings.
Matching in bipartite graph, Hall's Theorem Köenig's theorem.
Edge and vertex colourings, chromatic number and index number.
Properties of digraphs. Basic notion on Matroids