Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
2  
For the first problem, you may find Turan's Theorem useful. –  Austin Mohr Nov 7 '12 at 19:04
add comment

1 Answer 1

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

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

share|improve this answer
add comment

Your Answer

 
discard

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.