06690 - Graph Theory

Course contents

Definition and elementary properties of graphs. Simple graphs. Complete graphs. Bipartite graphs. Adjacency and incidence matrix of a graph.

Isomorphisms and automorphisms of a graph.

Elementary operations: union, intesection, difference. Subgraphs. Degree of a vertex. Regular graphs.

Paths and cycles. Connected components of a graph. Cut vertices and bridges.

Trees and forests: definition and charcterization. Spanning trees. Every connected graph has a gene rating tree and vice-versa.

Eulerian graphs. Euler Theorem.

Hamiltonian graphs

Grafi Hamiltoniani. Ore and Dirac Theorem.

Planar graphs. Dual graph of a planar graph. Euler formula. Planar graphs and polyhedra. The five regular polyhedra. Characterization of planar graphs.

Graph coloring. Chromatic number. Planar graph coloring. The five color theorem (with proof). The four color theorem (without proof). Chromatic polynomial of a graph.

Matching of a graph. Matching of a bipartite graph.

Connection number of a graph. Harary graph. Edge connection. Whitney theorem.

Directed graphs: definition and elementary properties. Flows in networks. Max flow – min cut theorem.

Readings/Bibliography

Reinhard Diestel. Graph Theory. Electronic Edition 2000 cс Springer-Verlag New York

Office hours

See the website of Marilena Barnabei