3. Recall that an independent set in a graph G is a set of vertices I in G such that no two vertices in I are adjacent (neighbors). The maax- imum independent set problem is, given a graph G, to compute an independent set of maximum size (maximum number of vertices) in G. Pinocchio claims that he has a greedy algorithm that solves the maximum independent set problem. Pinocchio's algorithm works as follows. The algorithm initializes the set I to the empty set, and re- peats the following steps: Pick a vertex in the graph with the minimum degree, add it to the set I, and remove it and all the vertices adjacent to it from the graph. The algorithm stops when the graph is empty. Does Pinocchio's greedy algorithm always produces a maximum inde- pendent set? Prove your answer (if it does, give a proof; if it does not, give a counter example, that is, a graph on which Pinocchio's algorithm does not produce a maximum independent set)