There is given complete graph $K_{n}$.
Let $A(n,k)=$minimal (in respect of its size) subset of edges of $K_{n}$ such every $k$-clique has at least one edge in common with this set.
Find formula for $|A(n,k)|$
I wrote down some examples such $|A(4,3)|=2$ But afterall i can not see the pattern.
Thank you in advance for help.
Oh, actually this is directly answered by Turán's theorem.
The theorem gives a construction for the $n$-node graph, called the Turán graph $T(n,k-1)$, which has the max number of edges $B(n,k)$ under the constraint that it is free of $k$-cliques. This is equivalent to saying that starting with $K_n$ you have to delete (color) as many edges as necessary to bring it down to $T(n,k-1)$. The construction is easy enough that you should be able to figure out $B(n,k)$ and therefore $A(n,k) = {n \choose 2} - B(n,k)$.