Ementa: Noções fundamentais da Teoria dos Grafos : caminhos, árvores e ciclos. Caminhos hamiltonianos e eulerianos. Grafos planares. Grafos e redes elétricas. Espaços vetoriais associados a grafos. Fluxos, conectividade, emparelhamento, colorações: fluxos em grafos orientados. Teorema de Menger, teorema de Tutte. Teorema das 5 cores, Teorema de Brooks, Teorema de Vizing. Grafos perfeitos: Teorema de Lovasz e algoritmos específicos. Teoria de Ramsey com aplicações à Álgebra, Geometria dos Números. Grafos Randômicos : Teorema de Erdos. Grafos e Grupos. Introdução à Teoria de Matróides.

Bibliografia:

• Bela Bollobas, Graph Theory, Springer-Verlag (1979).

• Bondy and Murty, Graph Theory With Applications, Elsevier (1976)

• M. Golumbic, Perfect Graphs and Algorithmic Graph Theory, Academic Press (1980)

• D. Welsh, Matroid Theory, Academic Press (1976)

• Sóstenes Lins, Princípios de Enumeração, Edições IMPA (1981)