H. I only need question 3 done! It involves discrete math! Let's consider an undirected graph Gthat for any vertices, i, j E I and there is no edge between i and į in E. A set i is a maximalindependent set if no additional vertices of V can be added to I without violating itsindependence. Note, however, that a maximal independent set is not necessarily the largestindependent set in G. Let a(G) denote the size of the largest maximal independent set in G.= (V,E). An independent subset is a subset I cV such Let's consider the following algorithm for generating maximal independent sets: starting with anempty set I, process the vertices in V one at a time, adding v to I is v not connected to any vertexalready in I.2. Argue that the output I of this algorithm is a maximal independent set3. Construct an example of a graph on n vertices such that running this algorithm on thevertices in one order yields an independent set of size 1, and processing the vertices in adifferent order yields an independent set of size n – 1, which is maximal.

Given: G = V , E is an undirected graph. An independent subset is a subset I ⊂V such that for any vertices i , j ∈ I, and there is no edge between i and j in E. A set I is a maximal independent set if no additional vertices of V can be added to I without violating its independence. Also, given an algorithm for generating maximal independent set, starting with an empty set I, process the vertices in V one at a time, adding v to I is v not connected to any vertex already in I. We have to construct an example of a graph on n vertices such that running this algorithm on the vertices in one order yields an independent set of size 1, and processing the vertices in a different order yields an independent set of size n-1, which is maximal.Here, we have to construct an example of a graph on n vertices such that running the algorithm (mentioned above) on the vertices in one order yields an independent set of size 1, and processing the vertices in a different order yields an independent set of size n-1, which is maximal. Let G = V , E be a graph with n vertices, v1 , v2 , … vn such that the edges v1vi ∈ E , ∀ i = 2,3, …, n and vivj ∉ E , ∀ i,j = 2,3, …, n. That is, v1 is connected to all other vertices of G and vi is not connected to any vertex of G, except v1 for i = 2,3, … , n. The figure of such graph is as follows: First, we are going to find an independent set of size 1. Let I = v1. If we add any other vertex vi of G to I, it violates the independence of I. Because v1vi is an edge of G, for i = 2, 3 , … , n. Therefore, I = v1 is the maximal independent set of size 1. Next, we are going to show that if we run the algorithm (mentioned above) on the vertices in a different order, it yields an independent set of size n-1, which is maximal. For example, let I1 = vi , for any vertex vi , i≠1. Without loss of generality, let I1 = v2. If we add v1 of G to I1, it violates the independence of I1 because v2v1 is an edge of G. If we add v3 of G to I1, it does not violate the independence of I1 because there does not exist an edge v3v2 of G. So, let I2 = v2 , v3. Then, I2 is an independent set. If we add v4 of G to I2, then it does not violate the independence of I2 . Because, there does not exist an edge v3v4 of G . So, let I3 = v2 , v3 , v4 . Then, I3 is an independent set. If we add v5 of G to I3, it does not violate the independence of I3 because there does not exist an edge v4v5 of G. So, let I4 = v2 , v3 , v4 , v5. Then, I4 is an independent set. Continuing like this, we get the following: In-1 = v2 , v3 , v4 , v5 , … vn is a maximal independent set with size n-1.