What is a(G) if G is a complete graphon n vertices? Consider an undirected graph G = (V, E). An independent set is a subset I CV such that for any vertices i, j e I,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 beadded to I without violating its independence. Note, however, that a maximal independent sent is not necessarilythe largest independent set in G. Let a(G) denote the size of the largest maximal independent set in G.

It is given that G is a complete graph on n vertices. Also provided are some basic definitions about independent set: Consider an undirected graph G = V , E. An independent set is a subset I⊂V such that for any vertices i , j∈I, there is no edge between i and j in E. A set I is a maximal independent set if no additional vertices of Vcan be added to I without violating its independence. Note, however, that a maximal independent set is not necessarily the largest independent set in G. Let αGdenote the size of the largest maximal independent set in G. We have to find αG for a complete graph G.It is given that G is a complete graph on n vertices. A complete graph is a graph G = E , V such that for any two vertices v1, v2 ∈V, there is an edge between them. Now, we are going to construct an independent set I. Choose an arbitrary vertex v∈V, say v1, and add it to I, i.e., I = v1. Then, by definition of the complete graph, v1 is adjacent to every vertex of G . So if we add any vertex from V to I , it violates the independence of I. Therefore, we can say that I = v1 is a maximal independent set, and there is some other largest maximal independent set in G . Hence αG = 1.