# Representing graphs with dictionaries

G = {'A': [], 'B': ['A', 'C'], 'C': ['A'], 'D': ['B']}


# Hamiltonian path

def hampath(graph):
    """Returns whether or not a Hamiltonian path exists in graph."""
    for vertex in graph:
        if hamiltonian(graph, vertex):
            return True
    return False

def hamiltonian(graph, vertex):
    """Returns whether or not a Hamiltonian path exists in graph
    starting from vertex.
    """
    def hamil_helper(v, visited):
        """Returns whether or not there is the rest of a Hamiltonian
        path starting from v, given the set of vertices already visited.
        """
        if v in visited:
            return False
        visited.add(v)
        if visited == set(graph):
            return True
        for next_v in graph[v]:
            if hamil_helper(next_v, visited):
                return True
        return False
    return hamil_helper(vertex, set())