Is there a redundancy between the two functions of adding a start node and an end node to my graph?
You can use the built-in getattr function to extract an attribute by name. Likewise the setattr function to set attributes.
This means you can pass the name of the attribute to a private function, unifying the code:
def _find_nodes_with_no(pred_succ: str, nodes: List[Node]) -&gt; List[Node]:
    &quot;&quot;&quot; Find nodes with either no predecessors, or no successors. &quot;&quot;&quot;

    if pred_succ not in (&quot;predecessors&quot;, &quot;successors&quot;):
        raise ValueError(&quot;pred_succ must be either 'predecessors' or 'successors'&quot;)

    return [node for node in nodes if not getattr(node, pred_succ)]

Your add_start and add_end functions can thus be written to pass the appropriate names:
def add_start(graph: Graph):
    info = (&quot;create_start_node&quot;, &quot;predecessors&quot;, &quot;successors&quot;)
    _add_outer_node(graph, info)

def add_end(graph: Graph):
    info = (&quot;create_end_node&quot;, &quot;successors&quot;, &quot;predecessors&quot;)
    _add_outer_node(graph, info)

Then in _add_outer_node you can do things like:
cmeth, main_links, back_links = info
create_method = getattr(Node, cmeth)
new_node = create_method(graph)

# ...

outer_nodes = _find_nodes_with_no(main_links, graph)

One thing I do question it your &quot;manual&quot; connection of both the predecessor and successor links. It seems like you want those to be reflexive, so why not create an add_predecessor method that automatically creates the reciprocal link? Likewise with add_successor?