algorithm to delete nodes that completely removes connectivity
Your problem is: given a graph, find a minimum-sized set of vertices whose removal disconnects the graph.

This is the "minimum vertex cut" problem.  There are standard algorithms for this, based on network flow and the max-flow-min-cut theorem.  You need to modify the graph slightly to make two copies of nodes, then apply network flow (network flow on the original graph finds a minimum edge cut; you want a minimum vertex cut).  See https://en.wikipedia.org/wiki/Vertex_separator, https://en.wikipedia.org/wiki/Cut_(graph_theory), https://cstheory.stackexchange.com/q/2877/5038.