What does a consistent heuristic become if an edge is removed in A*?
Consistency is a property of heuristics. You can think of consistency as the common sense idea that our guess at the time to go from $A \rightarrow B \rightarrow C$ cannot be more than the time to go from $A \rightarrow B$, plus our guess of the time to go from $B \rightarrow C$.

Supposing we remove a given edge $c(n,m)$ from our graph, but that our heuristic function gives the same value for $h(n)$ as before. Can the function be inconsistent? Let's try a proof sketch:


Since the function was consistent before we removed this edge, it must already be the case that $h(n) &lt; c(n, m') + h(m')$ for every other node $m'$ adjacent to $n$. 
Removing the edge $c(n,m)$ doesn't change these relationships, because the other edges still have the same costs as before, and the heuristic function still gives the same value for every node.
The same argument may be applied to node $m$.
Since none of these relationships have changed, $h$ is still consistent.