Minimum size of largest Clique in a Graph
I am trying to solve a programming challenge involving cliques, but am having a hard time wrapping my head around the mathematics behind the theory.
... what is the minimum size of the largest clique in any graph with N nodes and M edges.
Some sample output:
(N, M): answer
(3, 2) : 2
(4, 6) : 4
(5, 7) : 3
(6, 7) : 2
(35, 152): 2
I am having a hard time wrapping my head around why N = 35, M = 152 and N = 6, M = 7 results in the minimum clique of 2, wheras N = 4, M = 6 results in a minimum clique of 4.
No matter how I draw graphs of (6, 7) I always end up with Cliques of Size 3, if it was simply a matter of choosing the smaller value, we would always have clique size 2, but this is contradicted by (4, 6) giving a result of 4.
Can someone explain what I am missing in my understanding of graph theory to comprehend why (6, 7) = 2?
$\endgroup$ 12 Answers
$\begingroup$I will explain the answers for $(N,M) = (6,7)$ and $(5,7)$:
Firstly, as long as the number of edges $M>0$ there will always be a clique of size $2$, namely, the two connected vertices in (any) one of the edges.
Now label our six points $A,B,C,D,E,F$. Here is a graph with no cliques of size greater than 2 (which then proves that the minimu size of the largest clique is exactly 2):
Connect $A$ to $B$, $B$ to $C$, $C$ to $D$, $D$ to $E$, $E$ to $F$, $F$ to $A$, and $A$ to $D$. Notice that there are no cliques of size 3 or more. For example, in $(A,B,D)$ we are missing link $BD$.
On the other hand, if there were only five vertices (and still seven edges), it is easy to show there must be a clique of size at least 3. We do this by trying to construct a 3-clique-free $(5,7)$ graph.
Start by noting that $7$ edges times $2$ vertices connected per edge distributes $14$ connections among the five vertices, so some vertex must have at least 3 connections and some other vertex must have only 2 connections; label these $A$ and $E$ respectively. If $E$ has no connections then we are reduced to the case $(4,7)$ but no graphs of $4$ vertices have more than $6$ edges. If $E$ has only 1 connection then $ABCD$ forms a graph of $4,6)$ which is fully connected and has a clique of size $4>3$ So we can take $E$ to be connected to two exactly vertices.
Now assume $E$ is not connected to $A$; then $E$ is connected to two other vertices, label them $(C, D$. And $A$ is connected to $3$ vertices, which must be $B,C,D$. Consider vertex $B$. By the same reasoning as told us that $E$ must connect to $2$ vertices, $B$ must connect to at least one other vertex than just $A$; which must be $C$ or $D$; wlog we can label $C$ as a vertex $B$ connects to. But then $ACB$ is a 3-clique.
So to construct a 3-clique-free graph, $A$ must connect ot $E$. We can label such that $A$ connects to $B,C,E$. Then $E$ must also connect to some other vertex, and it cannot be $B$ or $C$ because that forms a click $EBA$ or $ECA$. So $E$ connects to $D$.
Now $B$ and $C$ must each connect to at least one other vertex, as before. they cannot connect to each other, and they cannot connect to $E$, without forming a 3-clique involving $A$. So they must both connect to $D$.
Now we have a 3-clique-free graph with $6$ edges so we need to add one more edge. But that edge cannot be $AD$ since that forms clique $ADE$. SO it would have to join two of $B,C,E$. But $BE$ or $BC$ form a 3-clique with $A$, and $CE$ forms a 3-clique with $D$. Therefore you cannot form a 3-clique-free $(5,7)$ graph.
$\endgroup$ $\begingroup$Here's your $G(6,7)$ with no triangles (i.e. maximum clique size $2$)...
As for $G(4,6)$, this is a description of $K_4$, so of course the clique number is $4$.
For $G$ with $n$ nodes, you can construct a graph with $\left \lfloor \frac{n^2}{4} \right\rfloor $ edges and no triangles by splitting the nodes as evenly as possibly into a bipartite graph. Specifically, you can construct $G(6,9)$ with a maximum clique of $2$ and likewise you can make $G(35, 306)$ with largest clique size $2$.
$\endgroup$ 1
