Dependency Graph - Acyclic graph
The deletion process has two phases, one for each condition.


Delete the specified node and all nodes that have a directed path to it.
Delete all nodes that have no incoming edges anymore and are no sources (iterate).


There are two imporant observations that make this correct:


During phase two, we create no new nodes with dangling outgoing edges, that is we do not break more dependencies that would cause nodes to be removed by condition 1.
Phase two is a fixed-point iteration.


How you would implement this depends on your graph representation. For example, if graphs have a node list, a list of sources and every node has lists of incident nodes via incoming (pred) and outgoing (succ) edges, respectively, you can do it like this:

  void removeFancy(g : Graph, n : Node) {
    rem = collectReverse(g,n)
    g.removeAll(rem)
    removeRedundant(g)
  }

  Node[] collectReverse(g : Graph, n : Node) {
    result = [n]
    foreach ( n' in n.pred ) {
      result ++= collectReverse(g,n')
    }
    return result
  }

  removeRedundant(g : Graph) {
    oldSize = 0
    while ( oldSize != g.size ) {
      oldSize = g.size
      for ( n in g.nodes ) {
        if ( n.pred.empty? &amp;&amp; !g.sources.contains(n) ) {
          g.remove(n)
        }
      }
    }
  }


You can also do it in a more recursive fashion:

  void removeFancy(g : Graph, n : Node) {
    for ( n' in n.pred ) {
      removeFancy(g, n')
    }

    succ = n.succ.copy
    g.remove(n)

    for ( n' in succ ) {
      if ( n'.pred.size == 0 ) {
        removeFancy(g, n')
      }
    }
  }


Here it is more challenging to see correctness because the two phases are interleaved. The essential argument is that nodes deleted in the second loop never cause new dependency breaks, therefore all nodes that have to be deleted because of condition 2 are identified thus by recursion spanned by the calls in the first loop.

If you apply any of those to your second example, you will see that in addition C, F, A and G also D will be deleted, but no other nodes.