# the minimum possible value of the order of a graph G which is a finite union of N-order complete graphs

Let $N$ be a positive integer,$G$ be a simple graph and $H_1,H_2,\ldots,H_k$ be a family of subgraphs of $G$ which satisfy:

1. every $H_i$ is a $N$-order complete graph;
2. the union of $H_i$ is $G$;
3. the maximal clique size of $G$ is $N$;
4. $H_i$ is not equal to $H_j$ and the intersection of $H_i$ and $H_j$ is not empty for any different $i$ and $j$;
5. the intersection of $H_i$ is empty.

I want to ask what is the minimum possible value of the order of G.

(Here for any two simple graph $G_1$=($V_1$,$E_1$) and $G_2$=($V_2$,$E_2$),define the union of $G_1$ and $G_2$ be (the union of $V_1$ and $V_2$ , the union of $E_1$ and $E_2$), the intersection of $G_1$ and $G_2$ be (the intersection of $V_1$ and $V_2$ , the intersection of $E_1$ and $E_2$).)

• What do you mean by: "5 the intersection of Hi is empty;"? Commented Sep 23, 2013 at 16:35
• I assume user40096 means that $\bigcap_{i=1}^k V(H_i)=\emptyset$. Commented Sep 23, 2013 at 16:54

Lemma. Let $G$ be a graph on $n$ vertices containing no $(k+1)$-clique. Then all $k$-cliques in $G$ have at least $2k-n$ common vertices.
This yields that $G$ should contain at least $2N$ vertices, otherwise the $H_i$ have a common vertex.
On the other hand, a complete graph on $2N$ vertices with a perfect matching removed contains no $(N+1)$-clique, but it contains $2^{N-1}$ pairwise intersecting cliques of size $N$. So, if $3\leq k\leq 2^{N-1}$, then the answer is $2N$.