F. I need help with this discrete math problem! Let's consider an undirected graph G = (V, E). An independent subset is a subset I C V suchthat for any vertices, i, j E I and there is no edge between i and j 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.1. What is a(G) if G is a complete graph on n vertices? What if G is a cycle on n vertices?

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. αG denotes the size of the largest maximal independent set in G. We have to find αG if G is a complete graph on n vertices and if G is a cycle on n vertices.Suppose that G is a complete graph on n vertices. We have to find αG. First, we need to find the largest maximal independent set in G. For that, let v be an arbitrary vertex in V. Let I = v. If we add any other vertex w from V to I, it violates the independence of I. Because G is complete. Therefore, for any vertices v and w, there is an edge between v and w in G. Thus, we can say that I = v is the largest maximal independent set in G. Hence, αG = 1.Suppose that G is a cycle on n vertices. We have to find αG. We are going to solve this problem in two cases. Case 1: n is even Let G = v1 v2 … vn v1. Since n is even, let n = 2m. Then, G = v1 v2 … v2m v1. First, we need to find a largest maximal independent set I in G. Let I1 = v, where v is an arbitrary vertex in V. With out loss of generality, let v = v1. If we add v2 from V to I1, it violates the independence of I1 because v1v2 is an edge of G. If we add v3 from V to I1, it does not violate the independence of I1 because v1v2 is not an edge of G. Therefore, I2 = v1 , v3 is an independent subset. If we add v4 from V to I2, it violates the independence of I2 because v3v4 is an edge of G. If we add v5 from V to I2, it does not violate the independence of I2 because v3v5 is not an edge of G. Therefore, I3 = v1 , v3 , v5 is an independent subset. Continuing like this, we get that Im = v1, v3 ,v5 ,… ,v2m-1 is an independent subset. If we add v2m from V to Im, it violates the independence of Im because v2m-1v2m is an edge of G. Therefore, Im = v1, v3 ,v5,…,v2m-1, a largest maximal independent set in G. Thus, αG is the size of Im. The number of elements in the arithmetic sequence x1 , x2 , … xn with common difference d is given by n =xn - x1d + 1. Now, consider v1, v3 ,v5,…,v2m-1 as an arithmetic sequence 1,3,5, … , 2m-1 with a common difference 2. Hence, αG = 2m-1-12+1 = 2m-22+1=m-1+1=m=n2=n2 , since n is even Case 1: n is odd Let G = v1 v2 … vn v1. Since n is odd, let n = 2m-1. Then, G = v1 v2 … v2m-1v1. First, we need to find a largest maximal independent set I in G. Let I1 = v, where v is an arbitrary vertex in V. Without loss of generality, let v = v1. If we add v2 from V to I1, it violates the independence of I1 because v1v2 is an edge of G. If we add v3 from V to I1, it does not violate the independence of I1 because v1v2 is not an edge of G. Therefore, I2 = v1 , v3 is an independent subset. If we add v4 from V to I2, it violates the independence of I2 because v3v4 is an edge of G. If we add v5 from V to I2, it does not violate the independence of I2 because v3v5 is not an edge of G. Therefore, I3 = v1 , v3 , v5 is an independent subset. Continuing like this, we get that Im-1 = v1, v3, v5 ,…, v2m-3 is an independent subset. If we add v2m-2 from V to Im-1, it violates the independence of Im-1 because v2m-3v2m-2 is an edge of G. If we add v2m-1 from V to Im-1, it violates the independence of Im-1 because v2m-1v1 is an edge of G. Therefore, Im-1 = v1 ,v3 ,v5 … ,v2m-3 is the largest maximal independent set in G. Thus, αG is the size of Im-1. Now, consider v1, v3 ,v5,…,v2m-3 as an arithmetic sequence 1,3,5, … , 2m-3 with a common difference 2. Hence, αG = 2m-3-12+1 = 2m-42+1=m-2+1=m-1=2m-12=n2 x denotes the greatest integer less than or equal to x. Hence, if G is a cycle on n vertices, αG = n2.