0
$\begingroup$

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

  • 2
    For the first problem, you may find Turan's Theorem useful.2012-11-07

1 Answers 1

2

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