Completude da pesquisa profunda em primeiro lugar

Cito de Inteligência Artificial: Uma Abordagem Moderna:

As propriedades da pesquisa profunda primeiro dependem fortemente do uso da versão de pesquisa em gráfico ou pesquisa em árvore. A versão de pesquisa de gráficos, que evita estados repetidos e caminhos redundantes, é completa em espaços de estados finitos porque, eventualmente, expandirá todos os nós. A versão de pesquisa em árvore, por outro lado, énã completo [...]. A pesquisa em árvore com profundidade inicial pode ser modificada sem custo adicional de memória, para que verifique novos estados com relação àqueles no caminho da raiz ao nó atual; isso evita loops infinitos em espaços de estados finitos, mas não evita a proliferação de caminhos redundante

Eu não entendo como a pesquisa de gráficos pode ser completa e a pesquisa em árvore não, sendo uma árvore um gráfico específic

lém disso, não entendo claramente a diferença entre "loops infinitos" e "caminhos redundantes" ...

lguém pode me explicar iss

ps. Para quem tem o livro, é a página 86 (3ª edição