Simplify an if else construct with assignment before if and else
def find_eulerian_tour(graph):
    available_edges, path = initial_state(graph)
    while incomplete(available_edges):
        edge = propose_extension_edge(available_edges, path)
        if extension_is_possible(edge):
            extend_path(available_edges, path, edge)
        else: 
            node = propose_node_for_reorder(available_edges, path)
            if reorder_is_sensible(node):
                path = reorder_path(available_edges, path, node)
            else:
                return None
    return path


Since you are inside a while block, an if-else can be turned into if->continue. The inner if-else can be turned into if not->return:

def find_eulerian_tour(graph):
    available_edges, path = initial_state(graph)
    while incomplete(available_edges):
        edge = propose_extension_edge(available_edges, path)
        if extension_is_possible(edge):
            extend_path(available_edges, path, edge)
            continue
        node = propose_node_for_reorder(available_edges, path)
        if not reorder_is_sensible(node):
            return None
        path = reorder_path(available_edges, path, node)
    return path


Now it reads like a checklist:


Extension possible? Do that and continue.
Reordering not sensible? Quit.
Reorder.


Is it an improvement? On the original: I think so. Nested logic is generally more difficult to follow. On the if-elif-else? Not really, but that's the price to pay for caching the intermediary values.