06690 - Graph Theory

Learning outcomes

By the end of the course, students will be able to explain the fundamental notions and principal results of graph theory, and to apply graph-theoretic methods to analyze problems arising in various areas of science and technology.

Course contents

Definition of a graph and of a simple graph. Degree of a vertex. Handshaking Lemma. Examples: complete graphs, cycles, wheel graphs, and cube graphs.

Subgraphs. Graph isomorphism.

Connected graphs. Connected components of a graph. Relationship between the number of edges and the number of vertices in a connected simple graph. Bridges and cut vertices. Bipartite graphs. Theorem: a graph is bipartite if and only if it contains no odd cycles.

Trees and forests. Theorem: every tree has at least two vertices of degree 1. Theorem: a tree with (n) vertices has (n-1) edges.

Cayley’s theorem on the number of trees with (n) vertices. Spanning trees. Theorem: every connected graph has a spanning tree. Depth-first search and breadth-first search algorithms.

Adjacency and incidence matrices of a graph. Basic properties. The Laplacian matrix of a graph. Matrix-Tree Theorem.

Eulerian graphs and their characterization. Fleury’s algorithm. Hamiltonian graphs. Ore’s theorem on Hamiltonian graphs. Dirac’s theorem.

Line graphs. Theorem: if a graph is Eulerian, then its line graph is both Eulerian and Hamiltonian.

Matchings in a graph: definition and examples. Perfect matchings. Maximal and maximum matchings. Augmenting paths. Necessary and sufficient condition for a matching to be maximum.

Matchings in bipartite graphs: Hall’s theorem and its consequences. Vertex covers. Relationship between the cardinality of a minimum vertex cover and that of a maximum matching. Examples.

Kőnig–Egerváry theorem: in a bipartite graph, the cardinality of a minimum vertex cover is equal to that of a maximum matching. Independent sets of vertices and edge covers. Relationships among the various cardinalities. Gallai’s theorem and its consequences.

Matchings in arbitrary graphs: examples. Algorithm for finding a perfect matching. Tutte’s theorem: necessary and sufficient condition for a graph to admit a perfect matching.

Planar graphs and plane graphs. Faces of a plane graph. Dual graphs of plane graphs.

Edge contraction. Euler’s formula for planar graphs and its consequences. Platonic solids.

Graph colorings. Chromatic number. Kőnig’s theorem: a simple graph has chromatic number 2 if and only if it is bipartite. Upper and lower bounds for the chromatic number of a graph. Heuristic coloring algorithm.

Optimal coloring of a simple graph obtained by solving a linear programming problem. Coloring of planar graphs. Five Color Theorem. Outline of the Four Color Theorem.

Chromatic polynomial of a simple graph and its properties: recurrence relation, monicity, and explicit interpretation of some of its coefficients. Tutte polynomial of a graph: definition, properties, and its relation to the chromatic polynomial.

Perfect graphs: definition and properties. Examples of perfect graphs: bipartite graphs. Comparability graphs of a partial order: Mirsky’s and Dilworth’s theorems. Lovász’s theorem: the complement of a perfect graph is perfect. The complement of a bipartite graph is perfect: connection with Kőnig’s theorem. The inversion graph of a permutation is perfect.

Vertex connectivity. Connectivity number of a graph. Upper bounds for the connectivity number. Harary graphs.

Edge connectivity and edge-connectivity number. Relationship between vertex connectivity, edge connectivity, and minimum degree. Cuts in a graph. Relationship between edge cutsets and cuts.

Networks. Flows in networks. Ford–Fulkerson algorithm for constructing a maximum flow. Max-flow min-cut theorem and its consequences.

Ramsey theory. Pigeonhole principle. Ramsey’s theorem. Lower and upper bounds for Ramsey numbers and explicit computation of some of these numbers.

Readings/Bibliography

Graph Theory with Applications by J.A. Bondy and U.S.R. Murty (North-Holland/Macmillan, 1976)

Lecture notes by Professors Casolo e Fumagalli available online.

Teaching methods

The course consists of lectures devoted to the presentation of definitions, examples, proofs, and applications. Throughout the course, a series of exercises will be assigned in order to consolidate the theoretical aspects of the subject.

Assessment methods

Assessment consists of an oral examination only. On a voluntary basis, students may present a recent research paper illustrating new results in graph theory. A list of possible papers may be provided by the instructor, or students may propose a paper of their own choice, subject to the instructor’s approval. This presentation may account for up to half of the final assessment. The remaining part of the examination will in any case include questions on proofs of selected theorems and on topics studied during the course.

Teaching tools

Blackboard lectures, exercise sheets, and supplementary teaching materials provided by the instructor.

Office hours

See the website of Riccardo Biagioli