Let G = (V, E) be an undirected non weighted graph. Say that a vertex v can see an edge if v is an endpoint of that edge. Say that a set S V is all-seeing if every edge e E is seen by at least one vertex in S. In this problem, we will try to greedily construct the smallest all-seeing set possible. Consider the following greedy algorithm to find an all-seeing subset:

(a) Prove that findAllSeeingSubset(G) always returns an all-seeing subset. [We are expecting: A rigorous proof.]

(b) Give an example of a graph on which findAllSeeingSubset(G) does not return a smallest all-seeing subset, for at least one way of choosing edges.

findAllSeeingSubset (G): s={} while G contains edges: choose an edge e = (u,v) in G S.add (u) S.add (v remove u and all of its adjacent edges from G remove v and all of its adjacent edges from G return S