Clique Number

The number of Vertices in the largest Clique of $G$, denoted $\omega(G)$. For an arbitrary Graph,

$$\omega(G)\geq \sum_{i=1}^n {1\over n-d_i},$$

where $d_i$ is the Degree of Vertex $i$.

References

Aigner, M. ``Turán's Graph Theorem.'' Amer. Math. Monthly 102, 808-816, 1995.