# Graph Theory: Clique concepts

I was trying to solve a basic clique problem but i have stucked at some following points:

• what is is the minimum size of the largest clique in any graph with N nodes and M edges

• To Find the largest clique in a graph

Please tell me difference between above two statement in the context of basic clique problem . I am newbie in Graph Theory

-
For the first problem, you may find Turan's Theorem useful. – Austin Mohr Nov 7 '12 at 19:04

Let $\mathscr{G}_{N,M}$ be the family of all graphs with $N$ nodes and $M$ edges. Each $G\in\mathscr{G}_{N,M}$ contains some cliques. Let $c(G)$ be the maximum number of nodes in any clique in $G$. The problem asks you to find
$$\min\{c(G):G\in\mathscr{G}_{N,M}\}\;.$$
In words: if a graph has $N$ nodes and $M$ edges, what is the smallest possible size of its largest clique?
A small example may help. Suppose that $N=M=6$. One of the graphs in $\mathscr{G}_{6,6}$ is the graph $G$ consisting of two disjoint triangles; each of those triangles is a clique of size $3$, so $c(G)=3$. But another graph in $\mathscr{G}_{6,6}$ is the circuit $C_6$ of $6$ nodes, like a necklace; its maximal cliques are pairs of adjacent vertices, so $c(C_6)=2$. You can’t have maximal cliques any smaller than that in a graph that has at least one edge, so
$$\min\{c(G):G\in\mathscr{G}_{6,6}\}=2\;.$$