Knowledge of the induction principle and its use in theory and applications. Knowledge of the main combinatorial and counting tools. Ability to set up, formalize and solve some typical counting and combinatorial problems. Knowledge, use and explicit resolution of linear recursions. Knowledge of the basic elements of graph theory. Ability to model concrete problems (for example planning events under certain constraints, optimizing the path between two locations, analyzing game strategies) using graphs with appropriate properties. Ability to translate some instances of concrete problems (for example recursive procedures or simple problems of tessellation and enumerative combinatorics) into the equivalent mathematical / combinatorial object.

The basic notions on sets, functions, and of calculus for functions in one variable are required

Correspondences and applications. Equivalence and order relations. Cardinality. The awell ordering axiom, strong and weak form of the induction principle. 8 hours First counting problems. Decision trees and recursive processes. Functions and counting, the pigeonhole principle, the product rule and the additive principle. Selections with or without order, with or without repetitions. Permutations, binomial and multinomial coefficients, binomial formula. Classic examples. The inclusion-exclusion principle and applications. 22 hours Linear recursions and applications. 8 hours Unoriented graphs, walks, paths and cycles. Eulerian walks and Hamiltonian cycles. Trees. Combinatorial graph. Planar graphs, the Euler formula and its corollaries, coloring problems and applications. Bipartite graphs, matching problems and applications. Adjacency matrix, outline on spectral theory for graphs, examples of spectrum. Lower estimates for complexity through decision trees and optimal strategies. Examples and applications, in particular to tessellation problems and sorting algorithms. Outline of direct and weight graphs. 22 hours

During the course many exercises are discussed and carried out by the teacher, covering all the topics of the course. For didactic and evaluation purposes, during the course, ongoing activities are proposed and monitored by the teacher such as, for example, the conduct of self-assessment tests and the resolution of problems, which require the active participation of the student. The modalities are made known by the teacher at the beginning of the course.

The course content is fully covered by lecture notes and other material (including examples and exercises carried out) prepared by the teacher and made available online to students enrolled in the course. For further information, any text entitled "Discrete Mathematics", "Graph Theory" or similar variants is suitable for the purpose. Some specific examples are as follows: L. Lovász e K. Vesztergombi , "Lecture Notes on Discrete Mathematics" (disponibile online). N. L. Biggs, "Discrete Mathematics". Clarendon Press, Oxford, 1985. A. E. Brower e W. H. Haemers, "Spectra of graphs". Springer, New York, 2012 K.H. Rosen. Discrete mathematics and its applications (7th edition) (disponibile online)

Exam: Optional oral exam; Paper-based written test with video surveillance of the teaching staff;

The exam consists of a written closed book examination, which lasts 90 minutes and consists of problems and questions (either multiple choice test, or open text questions) on all the topics of the course. The problems allow to check the ability of the student to solve problems using graph theory and the counting and combinatorics methods described in the course. The questions allow to check the knowledge of the theoretical part of the subject. Teaching material is not allowed during the exam. The maximum grade is 30 lode. During the written examination, the use of teaching materials, calculator, and electronic devices is not allowed, except those explicitly authorized. The oral exam is optional, it is held in the same session as the written test, it covers all the topics of the course, it can be requested by the student to improve the result obtained in the written test, or by the teacher if an in-depth study is appropriate. In the case of an oral test, the final grade is made up of the overall assessment of the written test and the oral test (which may increase or decrease vary the grade of the written test). The final assessment of the exam can be integrated up to a maximum of 3 out of 30 with the evaluation of the ongoing activities actually carried out by the student. Examples of problems and questions of previous written examinations are available on the web page of the course.

Exam: Written test; Optional oral exam; Paper-based written test with video surveillance of the teaching staff;

The exam consists of a written closed book examination, which lasts 90 minutes and consists of problems and questions (either multiple choice test, or open text questions) on all the topics of the course. The problems allow to check the ability of the student to solve problems using graph theory and the counting and combinatorics methods described in the course. The questions allow to check the knowledge of the theoretical part of the subject. Teaching material is not allowed during the exam. The maximum grade is 30 lode. During the written examination, the use of teaching materials, calculator, and electronic devices is not allowed, except those explicitly authorized. The oral exam is optional, it is held in the same session as the written test, it covers all the topics of the course, it can be requested by the student to improve the result obtained in the written test, or by the teacher if an in-depth study is appropriate. In the case of an oral test, the final grade is made up of the overall assessment of the written test and the oral test (which may increase or decrease vary the grade of the written test). The final assessment of the exam can be integrated up to a maximum of 3 out of 30 with the evaluation of the ongoing activities actually carried out by the student. Examples of problems and questions of previous written examinations are available on the web page of the course.