Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
For the first problem, you may find Turan's Theorem useful. – Austin Mohr Nov 7 '12 at 19:04
up vote 2 down vote accepted

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


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


share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.