Artificial intelligent assistant

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`

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\;.$$

xcX3v84RxoQ-4GxG32940ukFUIEgYdPy f3780e5a94373fe37bd802e0aae19cda