elaborando

Soluzione ricevuta da peppe, via email:
ce ne sono otto, perche' da A posso arrivare ad esempio in D in due modi (ACD o AFCD) e altrettanti per E, e da li' in B in due modi, ovvero:
(DB o DEB): 2 * 2 * 2 = 8.
considerando che i vertici di partenza e arrivo hanno grado 2, e quelli intermedi 3, si vede subito che in nessuno dei vertici intermedi si puo' passare piu' di una volta.

ne deriva che i percorsi massimi possono passare al piu' per 6 vertici. e quelli minimi per 4.

mettendo tutto insieme, se su linux si da' questo comando,

echo A{A..F}{A..F}B A{A..F}{A..F}{A..F}B A{A..F}{A..F}{A..F}{A..F}B |
tr ' ' 'n' |
grep -v '([A-F]).*1' |
egrep -v 'AB|BA|CE|EC|DF|FD|AD|DA|AE|EA|BC|CB|BF|FB'

l'output e' l'elenco dei cammini possibili:
ACDB
AFEB
ACDEB
ACFEB
AFCDB
AFEDB
ACFEDB
AFCDEB

- la prima riga genera tutte le possibili sequenze di 4, 5 o 6 vertici con inizio in A e fine in B (sfruttando la cosiddetta "brace expansion" della bash)
- la seconda trasforma gli spazi in ritorni a capo, in modo da avere una sequenza per linea
- la terza esclude le sequenze con vertici ripetuti
- la quarta elimina le sequenze con collegamenti inesistenti.

non e' generalizzabile a grafi piu' complicati, perche' sfrutta i vincoli posti da questo problema, ma e' un modo veloce per verificare. ovvero, tanto rumore per nulla...

ciao
peppe