Problem $6$:a$.$ In a given undirected graph G$,$ an independent set of G is any

subset S of nodes in G such that there are no edges between the

nodes of S$.$ The independent set problem is the problem of finding a

maximum$-$size independent set in an input undirected graph G$.$ Give a

greedy algorithm for this problem, and prove by a counter example

that the Greedy solution is not always optimal.b$.$ In a given undirected graph G$,$ a vertex cover of G is any

subset C of nodes in G such that every edge in G involves at least

one node in C$.$ The vertex cover problem is the problem of finding a

minimum$-$size vertex cover in an input undirected graph G$.$ Give a

greedy algorithm for this problem, and prove that the Greedy

solution is not always optimal