Conexidade, caminhos, circuitos e traçar um grafo

Os grafos não fazem parte do programa de Matemática do ensino básico em Portugal; este estúdio é uma extensão (surgem no ensino secundário, em Matemática Aplicada às Ciências Sociais). Depois dos vértices, das arestas e do grau, vêm o caminho (uma sequência de arestas em que cada uma começa onde a anterior acabou), o circuito (um caminho que volta ao ponto de partida) e a conexidade (quaisquer dois vértices estão ligados por um caminho). Todo o grafo se divide em componentes conexas.

Um caminho de Euler usa cada aresta exatamente uma vez. Existe quando o grafo é conexo e tem zero ou dois vértices de grau ímpar. Com zero, existe um circuito de Euler (volta ao início); com dois, o caminho começa num e acaba no outro. É assim que se resolve o problema das pontes de Königsberg (quatro vértices ímpares) e a pergunta «consegues desenhar a figura sem levantar o lápis?».

Erros frequentes: não contar um vértice isolado como componente; contar vértices em vez de arestas para obter o grau; pensar que qualquer figura se pode desenhar de um só traço.