Considere o seguinte grafo planar topológico G de ordem 16.

Este grafo tem três tipos de arestas, paralelas aos vectores v, h e d, a que chamaremos respectivamente: arestas verticais, arestas horizontais e arestas diagonais. Chamaremos caminho a uma cadeia de G onde as arestas sejam percorridas na mesma direcção e sentido dos vectores acima. Conhecida a extremidade inicial, cada caminho fica univocamente descrito por uma palavra no alfabeto {V,H,D}, isto é por uma sequência de letras neste conjunto.
  1. Dados três números inteiros p, q e r, quantas palavras, neste alfabeto de três letras, se podem escrever usando p vezes a letra V, q vezes a letra H e r vezes a letra D?
  2. Para que valores de p, q e r as palavras da alínea anterior descrevem caminhos ligando os vértices A e C?
  3. Quantos caminhos existem com extremidade inicial no vértice A e extremidade final em C?
  4. Quantos caminhos de comprimento 3 existem?