Este texto é uma breve introdução à Teoria dos Grafos. Para embarcar nessa introdução, o leitor só precisa ter alguma familiaridade com demonstrações matemáticas formais e com a notação básica da teoria dos conjuntos elementar. A teoria dos grafos estuda objetos combinatórios—os grafos—que são um bom modelo para muitos problemas em vários ramos da matemática, da informática, da engenharia e da indústria. Muitos dos problemas sobre grafos tornaram-se célebres porque são um interessante desafio intelectual e porque têm importantes aplicações práticas. Nesta breve introdução, vamos nos restringir a quatro temas intimamente relacionados: conjuntos estáveis, coloração de vértices, emparelhamentos e coloração de arestas. Muitos outros temas e problemas, podem ser encontrados nos livros de Bondy–Murty [BM76], Wilson [Wil79], Diestel [Die00], Bollobás [Bol98], Lovász [Lov93], Lovász–Plummer [LP86], Lucchesi [Luc79] e Biggs–Lloyd–Wilson [BLW76]. Mesmo numa breve introdução como esta, é inevitável esbarrar em questões de complexidade computacional, pois muitos dos problemas da teoria dos grafos têm motivação algorítmica. O leitor interessado em aprofundar seus conhecimentos nessa área pode consultar os livros de Garey–Johnson [GJ79], Harel [Har92] e Sipser [Sip97].