Árvores são grafos conexos e acíclicos e formam uma das classes mais fundamentais e bem estudadas de grafos [1, 2, 3, 9, 10].

           Uma árvore geradora H de um grafo conexo G é um subgrafo conexo e acíclico de G com V(H)=V(G).

           Um problema de contagem relacionado é o de determinar o número de árvores geradoras. O trabalho pioneiro no assunto foi o de Cayley [4] sobre o número de árvores com vértices {1, 2, . . ., n}. É conhecida uma fórmula para este número e várias destas provas encontra-se em [6].

           Consideremos uma variante deste problema de contagem, que consiste do número de árvores com algumas arestas proibidas. Este é o caso de número de árvores geradoras de um grafo dado. Também é conhecida uma fórmula, baseada em espaços vetoriais associados aos ciclos dos grafos, para determinar o número de tais árvores [2, 3]. A aplicação desta fórmula para classes especiais de grafos tem sido considerada, como por exemplo em [5, 7, 8, 11].