I'm cracking up at this (working!) code that I'm about to start cleaning up. Please enjoy.
path_already_has_double_visited_small = any([path_so_far.count(x) == 2 for x in path_so_far if x.islower()])
for connection in nodes[last].connections:
if connection != 'start' and (connection.isupper() or connection not in path_so_far or (len([x for x in path_so_far if x == connection]) < 2 and not path_already_has_double_visited_small)):
explore(path_so_far + [connection])
Edit: So programmer girls don't unfollow me:
no_doubles = all(explored.count(x) < 2 for x in explored if x.islower())
for connection in nodes[last].connections:
if connection == 'start':
continue
if connection.isupper() or connection not in explored or no_doubles:
explore(explored + [connection])