
Course unit
GRAPH THEORY
INP9087848, A.A. 2019/20
Information concerning the students who enrolled in A.Y. 2019/20
Mutuating
Course unit code 
Course unit name 
Teacher in charge 
Degree course code 
SC04105572 
DISCRETE MATHEMATICS 
MICHELANGELO CONFORTI 
SC1159 
ECTS: details
Type 
ScientificDisciplinary Sector 
Credits allocated 
Educational activities in elective or integrative disciplines 
MAT/09 
Operational Research 
6.0 
Course unit organization
Period 
Second semester 
Year 
1st Year 
Teaching method 
frontal 
Type of hours 
Credits 
Teaching hours 
Hours of Individual study 
Shifts 
Practice 
3.0 
24 
51.0 
No turn 
Lecture 
3.0 
24 
51.0 
No turn 
Prerequisites:

basic knowledge of mathematics (including proof techniques, basic combinatorics etc.) 
Target skills and knowledge:

Knowledge of the basic results in graph theory; Understanding and applying proof methodologies andtechniques that are common in discrete mathematics. 
Examination methods:

Written exam. 
Assessment criteria:

Knowledge of the material presented in class. Authonomous application of proof techniques. 
Course unit contents:

Undirected graphs: Basic Definitions: walks, paths, cuts, connectivity. Classes of graphs: Bipartite, complete, kregular, hypercubes.
Trees: Definitions, basic properties, fundamental cycles, minimum spanning tree: Kruskal's algorithm.
Bipartite Matchings: Definitions, alternatingaugmenting paths. Hall's theorem, Konig's theorem, stable matchings.
General Matchings: Tutte's theorem, Berge's formula, Gallai's identities.
Directed Graphs: Basic definitions and properties. Strong connectivity, strongly connected components, acyclic digraphs, Tournaments, Hamiltonian paths and cycles in tournaments, GallaiMilgram theorem, comparability graphs.
Connectivity: Edge and vertex connectivity, 3 Menger theorems, ear decompositions.
Graph Coloring: EdgeChromatic number, Vizing's theorem, Chromatic number.
Planarity. Plane drawings and dual graphs, Euler's formula, colorability of planar graphs, Kuratowski theorem , Tait's theorem.
Traversability. Hamiltonian and Eulerian Graphs. 
Planned learning activities and teaching methods:

24 lectures of 2 hours each. 
Additional notes about suggested reading:

Detailed information can be found in
https://sites.google.com/view/micheleconforti/teaching 
Textbooks (and optional supplementary readings) 

Bondy, John Adrian; Murty, U. S. R., Graph theory. New York: Springer, .

Bollobas, Bela, Modern graph theory. New York: Springer, .


