PGEE 2018

Question

Maximal Independence Number is the cardinality of maximal independence set ( Independence set V of graph G is set in which no vertex of the set have a direct edge between them).

1) Maximal Independence Number of a complete graph is n-1

2) Maximal Independence Number of a complete bipartite  graph is $\frac{n}{2}$

3) Maximal Independence Number of a complete graph is 1

4)  Maximal Independence Number of complete graph is $\geq \frac{n}{2}$

Answer 1

3) Maximal Independence Number of a complete graph is $1 $

Pick any vertex $v$ from complete simple graph and then no other vertex can be part of the set because $v$ is connected to all other vertices.

Answer 2

independent set- siven a graph g=(v,e), s$\subseteq v$ is an independent set if there is no edges between vertex in s

in complete graph all vertex have a direct edge between them. so maximal independent set must be 1.Pick any node and that is the maximal independent set, because by definition of a complete graph it is connected to all other nodes.