Informalmente, um grafo pode ser visto como um conjunto de pontos, chamado vértices, e outro de pares desses pontos, chamados arestas. Cada aresta liga um par de pontos (extremidades) que a determina. Observe um exemplo simples de um grafo ao lado.

A Teoria dos Grafos tem uma origem relativamente recente (século XVIII) na história da Matemática. Apesar de sua definição formal só surgir no século XX, a resolução de Leonhard Paul Euler para o Problema das Pontes de Königsberg, publicada em 1736, é referida como a primeira publicação sobre a Teoria dos Grafos.

O problema acima mencionado é baseado na cidade de Königsberg, que é constituída por quatro áreas de terra,sendo elas duas ilhas e duas margens. Tais áreas eram, por sua vez, cortadas pelo Rio Prególia, sobre o qual havia, na época de Euler, as famosas Sete Pontes ligando-as, conforme mostra a figura abaixo.

A cidade de Konigsberg ficava na Prússia, região leste da Alemanha. Hoje, ela se chama Kaliningrad, e pertence à Rússia. Das sete pontes originais, uma foi demolida e reconstruída em 1935, duas foram destruídas durante a Segunda Guerra Mundial e outras duas foram demolidas para dar lugar a uma única via expressa. Assim, atualmente apenas duas pontes são da época de Leonhard Euler.

Enfim, discutia-se nas ruas da cidade a possibilidade de atravessar todas as pontes sem repetir nenhuma. Havia-se tornado uma lenda popular a possibilidade da façanha quando Euler, em 1736, provou que não existia caminho que possibilitasse tais restrições.

Euler montou um diagrama com o mapa da cidade, transformou os caminhos em retas e suas intersecções em pontos. Assim, Euler associou cada ilha e margem a um ponto que chamaremos de vértice e a cada caminho (ponte) uma ligação, que chamaremos de aresta.

Euler então percebeu que existiam vértices com exatamente três arestas incidentes. Por outro lado, como os moradores queriam atravessar cada ponte apenas uma vez, cada vértice deveria ter um número par de arestas. Logo, se tornaria impossível fazer um percurso seguindo as regras impostas pelos moradores. E com isso Euler chamou atenção para uma noção muito simples, que é a ordem de um vértice do grafo.

Repare que este diagrama constitui o primeiro exemplo de um grafo a ocorrer como modelo matemático para resolver um problema.