Università Roma Tre

Graphs: basic definitions. Simple and non simple graphs, planarity, connectivity, degree, regularity, incidence and adjacency matrices. Examples of families of graphs. The '' handshaking lemma ''.
Graphs obtained from others: complement, subgraph, cancellation and contraction. Isomorphisms and automorphisms of graphs. Connectivity: paths, cycles. A graph is bipartite if and only if each cycle has equal length.
Connetivity and connected component. Connectivity for sides and vertices. Eulerian and semi-Eulerian graphs.
Euler's theorem: a connected graph is Eulerian if and only if every vertex has an even degree. Hamiltonian graphs. Sufficient conditions to guarantee that a graph is Hamiltonian: the theorems of Ore and Dirac.
the Ore theorem. Trees and forests. The cyclomatic number and the "cutset" rank of a graph.
Fundamental system of cycles and cuts associated with a generating forest. Enumeration of generating forests. The Cayley theorem.
Generating trees: the "greedy" algorithm for the "connector problem". Planar graphs. K3,3 and K5 are not planar. Statement of the theorem of Kuratovski and variations.
Euler's formula for planar graphs. The dual of a planar graph.
Correspondence between cycles and cuts for planar graphs and their dual. Dual abstract. A graph that admits a dual abstract is planar. Colorings: initial considerations and some properties.
Colorings: the 5 colors theorem. Graphs on surfaces: classification of topological surfaces.
Coloring of faces and duality between this problem and the coloring of vertices. Reduction of the proof of the 4-color theorem to the coloring of cubic graph faces. '' The marriage problem ": Hall's theorem.
Hall's theorem in the language of transversals. Criteria of existence of transversal and partial transversivities. Application to the construction of Latin squares. Direct graphs: basic notions and orientability.
The Max-Flow Min-Cut theorem and Menger's theorem.
Complexity of algorithms and applications to the theory of graphs.
Introduction to the theory of matroids: definitions using bases and independent elements. Graphical and cographic matroids, vector matroids and the problem of representability.
Definition of matroid using the cycles and the rank function. Minors of a matroid. Transverse matroids and the Rado Theorem for matroids.
Union of matroids and applications: existence of disjoint bases in a matroid. Duality for matroids and applications to graphic and cographic matroids. Planar matroids and the generalization of Kuratovski's theorem for matroids.
Elements of algebraic graph theory: the incidence matrix and the Laplacian matrix of an oriented graph. The vertex space and the space of edges of a graph. Subspaces of the cycles and subspace of the cuts of a defined oriented graph of the incidence matrix.
Basis for the space of the cycles and for the space of the cuts of a graph. The Riemann-Roch theorem for graphs.
Proof of the "generalized Matrix Tree theorem". The contraction / restriction algorithm for matroids. Examples. The number of acyclical orientations of a graph.
Graph polynomials: the chromatic polynomial, the "reliabiliaty" polynomial. Examples. The polynomial rank of a matroid. Properties and first applications.
Proof of the structure theorem for functions on matroids that satisfy contraction/restriction properties. Their incarnation through the polynomial rank.
Whitey's moves and two isomorphisms for graphs. Isomorphism between graphical matroids implies isomorphism between graphs in case the graphs are 3 connected.
Whitney's Theorem for graphic matroids: sketch of the demonstration. Characterization for minors excluded from binary and regular matroids. The theorem of Seymour.

R. Diestel: Graph theory, Spriger GTM 173.
R. Wilson: Introduction to Graph theory, Prentice Hall.
B. Bollobas: Modern Graph theory, Springer GTM 184.
J. A. Bondy, U.S.R. Murty: Graph theory, Springer GTM 244.
N. Biggs: Algebraic graph theory, Cambridge University Press.
C. D. Godsil, G. Royle: Algebraic Graph theory, Springer GTM 207.
J. G. Oxley: Matroid theory. Oxford graduate texts in mathematics, 3.