Prove that GRAPH-SEARCH satisfies the graph separation property illustrated in Figure 3.9. Begin by showing that the

Question:

Prove that GRAPH-SEARCH satisfies the graph separation property illustrated in Figure 3.9. Begin by showing that the property holds at the start, then show that if it holds before an iteration of the algorithm, it holds afterwards. Describe a search algorithm that violates the property.

Figure 3.9.