Hamiltonian Path Algorithm on Directed Unweighted Graph uses non-existent edges

Question

I am trying to implement the Held-Karp algorithm for finding a Hamiltonian path on an unweighted directed graph. In order to achieve this I have created an inner class Combination which stores a Stack which represents the order of the path taken and a Set which stores the elements currently in the path.

The definition of a Hamiltonian Path is a path which visits every vertex in a graph only once

I am also using a queue to store the paths that have not yet been fully explored or discounted by the algorithm.

Initially this queue is filled with Combinations which each contain a single vertex in the graph. This fulfills the base case for Held-Karp where the trivial Hamiltonian path is a path which passes through a single vertex.

While the queue isn't empty the element from the front of the queue is dequeued. The top element from its stack is peeked as this element represents the last vertex added to the path. The adjacent vertices of the last vertex are looped through and if any of them are not in the current path set a new Combination object is created with the previous path Stack and path Set and the new vertex is added to the Stack and Set. This new Combination object is added to the back of the queue for later analysis. If it is not possible to add another vertex to a path then the loop continues and the reference to this Combination object is lost - the Combination is discounted.

If when dequeuing we come across a Combination object with a Stack with the same length as the number of vertices in the graph then we return an array representation of that Stack as it is a Hamiltonian path.

I am testing this algorithm against this Graph.

The adjacency list my code has generated for this graph is below:

[[1], [2, 3], [4], [4], [5], []]

And the key mappings between the matrix indices and vertex values are:

{0=F, 1=A, 2=B, 3=D, 4=C, 5=E}

    public String[] getHamiltonianPath() {
        String hamiltonianPath[] = new String[adjacencyList.size()];
        Combination newCombination;
        for(int i = 0; i < adjacencyList.size(); i++) {
            LinkedList<Combination> combinations = new LinkedList<>();
            // create base case with paths of length 1 including only a single vertex.
            for(int j = 0; j < adjacencyList.size(); j++) {
                combinations.add(new Combination(j));
            }
            while(!combinations.isEmpty()) {
                Combination current = combinations.pollFirst();
                // If we've found a Hamiltonian Path return it.
                if(current.pathOrder.size()  == adjacencyList.size()) {
                    while(!current.pathOrder.isEmpty()) {

                        hamiltonianPath[current.pathOrder.size() - 1] = ids.get(current.pathOrder.pop());
                    }
                    return(hamiltonianPath);
                }
                // Select the last vertex added to the path
                int lastVertex = current.pathOrder.peek();
                // Get all the vertices adjacent to the last vertex added to the path
                HashSet<Integer> neighbours = adjacencyList.get(lastVertex);

                for(int neighbour : neighbours) {
                    // Create a new combination for each path that includes the previous path
                    // and is extended to one of the adjacent vertices to the last vertex added.
                    newCombination = new Combination(current.path, current.pathOrder);
                    // Check if the adjacent vertex is already on the path.
                    // If so do not add it to the path
                    if(!newCombination.path.contains(neighbour)) {
                        newCombination.path.add(neighbour);
                        newCombination.pathOrder.push(neighbour);
                        // Add the new combination to the combinations queue
                        // for further extension later
                        combinations.add(newCombination);
                    }
                }
            }
        }
        return(hamiltonianPath);
    }


    public class Combination {
        HashSet<Integer> path;
        Stack<Integer> pathOrder;


        public Combination(HashSet<Integer> path, Stack<Integer> pathOrder) {
            this.path = path;
            this.pathOrder = pathOrder;
        }

        public Combination(int origin) {
            path = new HashSet<>();
            pathOrder = new Stack<>();

            path.add(origin);
            pathOrder.push(origin);
        }
    }

The ids HashMap is simply a mapping between the integer IDs of the vertices and their actual String values.

As this graph doesn't contain a Hamiltonian path I would expect the output to be an array of null Strings. However the output I actually get is:

F -> A -> B -> D -> C -> E

Which is very strange as there is no edge between B and D in the graph or the matrix.