When inserting a new vertex in a DAG, what possible changes are there to the edges

Question

Background: I'm trying to program a generic method to add a node to a Directed Acyclic Graph. This method should allow the caller to specify the possible effects on the graph, specifically the edges.

So far, I have identified the following possible changes, but I'm not sure if this set is complete.

1. Add a new edge from an existing node to the new node
2. Add a new edge from the new node to an existing node
3. Change one existing edge to point to the new node, keeping the existing tail
4. Change one existing edge to originate from the new node, keeping the existing head
5. Splice in the new node between two existing nodes, removing the original direct edge and replacing it with two new edges.

Of course, combinations of these changes are also possible. But is this set of changes complete? My problem in proving the completeness of this set of operations is relating the old and new set of edges. I think it's obvious that changes 1 and 2 keep the old graph as a subgraph of the new graph; changes 1,2 and 5 do not decrease reachability of the existing nodes, but you can create new reachability if you combine changes of type 1 & 2. Changes 3 and 4 can decrease reachability, not increase it.

Just for clarity: I do not consider changes to "unrelated" edges, e.g. adding a new edge between two existing nodes is out of scope.

Answer 1

Based on the comments, I missed one case:

6. Add an unconnected node.

I considered another approach to answering the same question. Consider the set of edges E in the original graph, and the set E' after adding the new node. How do these differ?

The missed case was the edge case E=E'. If the two sets are not equal, there are either edges in E that are not in E', edges in E' that are not in E, or both.

The "no unrelated changes" requirement means that any new edge starts or ends in the new node. It also means that an edge which existed in E but not in E' was not simply removed, but changed, and therefore there must also exist a corresponding new edge in E'.

Hence, we have two possible explanations for new edges in E', but only one explanation for edges that have gone missing from E. So if N is the number of new edges in E', and M is the number of missing edges from E, then we know N>=M. We can match M out of the N new edges to the M missing edges; each of these M pairs of (old edge, new edge) represents a "changed" edge. (This might not be a unique pairing). This will leave N-M edges that are entirely new.

We can split the M changed edges further in two groups; those edges that were changed to point to the new node and those that were changed to originate at the new node. (per the "no unrelated changes" assumption). Similarly, we can divide the new edges in two groups.

At this point, we have found back the categories 1-4 from the original answer. As noted in the comments, the 5th category (spliced in) can be represented as a combination of changes 1+4 or as the combination 2+3. It can make sense to semantically identify this as a unique change, because splicing in one node keeps the graph connected (and it remains a DAG). This gives us the full set of 6 change types that were identified before.

I have intentionally ignored adding edges that both originate and terminate at the new node, because that type of change certainly introduces a cycle. No other single change will introduce a cycle, but it's fairly obvious that if the old DAG had at least one edge, you can trivially add a new node and two new edges to introduce a cycle containing that original edge.