Number of maximum cliques in $n$- partite graph woth $2n$ vertices

46 Views Asked by At

Going through particular examples, it appears to me that a maximum clique of $n$-partite graph $G$ on $2n$ vertices is $n$-clique (clique of order $n$), when each partite contains exactly $2$ vertices. And the number of $n$-cliques in $G$ is $2^n$ (at most). So,

What is the formula to calculate the number of $n$-cliques in $G$? Where $G$ is $n$-partite graph on $2n$ vertices and each partite contains exactly $2$ vertices.

1

There are 1 best solutions below

0
On BEST ANSWER

If the parts have size $a_1,a_2,\dots,a_n$ then the number of cliques of size $n$ is equal to $a_1a_2\dots a_n$ because we must select one vertex in each clique.

by AM-GM we have $a_1a_2\dots a_n \leq (\dfrac{a_1+\dots + a_n}{n})^n = 2^n$ with equality when each $a_i$ is $2$.