Se você deseja ter uma breve definição, não custa nada consultar a boa e velha wikipedia (http://pt.wikipedia.org/wiki/Teoria_dos_grafos).
No entanto, se você deseja consultar um material com maior rigor matemático, eu recomendo fortemente o livro "Uma Introdução Sucinta à Teoria dos Grafos", dos professores Yoshiko Wakabayashi, Yoshiharu Kohayakawa e Paulo Feofiloff, todos do Instituto de Matemática e Estatística da USP.
O material encontra-se disponível para download e você pode buscar mais informações nas páginas abaixo:
http://www.ime.usp.br/~pf/teoriadosgrafos/
No link abaixo, você encontra vários exercícios sobre o mesmo assunto, organizados pelo prof. Paulo Feofiloff:
http://www.ime.usp.br/~pf/grafos-exercicios/
E nesse outro link você encontra mais uma série de links de livros (dessa lista, recomendo fortemente o livro Graph Theory with Applications, de Bondy e Murty. Esse livro também está disponível para download, porém seu conteúdo está em inglês).
http://www.ime.usp.br/~pf/grafos-exercicios/bib.html
Para completar as dicas, recomendo mais dois links de material on-line, mas esses não conheço bem:
- Material das profas. Graça Pimentel e Maria Cristina, do Instituto de Ciências Matemáticas e de Computação (ICMC) da USP: http://www.icmc.usp.br/manuals/sce183/grafos.html
- Material do prof. Antonio Carlos Mariani, do depertamento de Informática e Estatística (INE) da UFSC: http://www.inf.ufsc.br/grafos/livro.html
Espero que gostem! Bom estudo!
