Notes on graph theory and combinatorics by Prof. C. Casolo, a.a. 2016-17, to be found at http://web.math.unifi.it/users/casolo/
Learning Objectives
To get acquainted with fundamentals of graph theory and its applications.
Relations between graph theory and combinatorics.
Prerequisites
Nothing
Teaching Methods
Lessons and seminars.
Further information
The course appears on Moodle
Type of Assessment
Oral exam with a preliminary written exercise. For the final evaluation it is taken into account the participation to the seminars.
Course program
Graphs and multigraphs, degree, Handshake lemma, regular graphs. The Erdos-Gallai Theorem. Graph automorphisms and complementary graph. Vertex-deleted and edge-deleted subgraphs. Walks, trials, paths, circuits and cycles. Eulerian and hamiltonian graphst. Ore theorem and Dirac Theorem. Invariants: diameter and girth, stability index, clique number, cromatic number. Invariants and subgraphs.
Pigeonhole principle. Mantel Theorem and e Reiman Theorem.
Posets, chains and antichains. Dilworth Theorem and Mirsky Theorem.
Finite geometries and Gauss coefficients. Theorems for projective geometries associated with a field. Axiomatic version of projective plane. Theorem of Bruck and Ryser. Order of a projective plane. Fano plane.
Trees and minimum connector problem. Kruskal Algorithm. Kuratowski theorem. Non planarity of K_5 e K_3,3. Petersen graph as a toroidal graph.
Planar graphs. Four colour map theorem.
Bipartite graphs and their characterization. Matching problems and Hall's Marriage Theorem. Maximum and optimal matchings. Order relation associated with a poset. The influence of Dilworth Theorem. Konig Theorem.
Directed graphs and weighted directed graphs. Flows and networks. Cuts and augmenting path algorithm.The Ford and Fulkerson Theorem.
Connectivity and Menger Theorem. Problems on convergence for the augmenting path algorithm when capacities are real numbers.
Adjacency matrix. Cayley graphs and other graphs associated with finite groups.
Problems of combinatorics revisited by graph theory.
The program could slightly change, in relation to the interests of the students. The notes could also change.