A remark on the weak Turan's Theorem

Abstract

A subset $S$ of vertices of a graph $G$ is an \textit{independent set} if no pair of vertices of $S$ are adjacent. The \textit{independence number}, $\alpha(G)$ of $G$, is the maximum cardinality of an independent set of $G$. In this note, we present an improvement of the weak Tur$\acute{a}$n's theorem.

Keywords

• Independent set
• Turan's Theorem
• Probabilistic methods