There is given $k$-partite graph $G$, where independent sets have following cardinalities: $n_{1},n_{2},...,n_{k}$ We say that $k$-clique is marked if has at least one edge from given set of edges $A$.
Find $A$, such every $k$-clique in $G$ is marked.
Writing "find" i mean : find algorithm to construct that set, find the number $|A|$, find other properties such as the highest degree of some vertex.
I tried to apply Turan graphs for $k-1$ partite graph, then use it for every selected subset of independent sets. But it does not work. For example for $k=4$; $n_{1}=n_{2}=n_{3}=n_{4}=2$.
Any ideas how to solve it?
HINT (in case this is homework)
The given graph $G$ is clearly inspired by Turan, but you don't need the theorem, nor another Turan graph (e.g. with $k-1$ parts). Instead, inspired by Turan's reasoning, what can you say about:
Is there any $(k+1)$-clique in $G$?
There are $k$-cliques in $G$. Can you characterize them in some way?
Finally, if $A$ is such that every $k$-clique is marked, that also means if all edges in $A$ are removed, then there will be no more $k$-cliques. Perhaps this is an easier way to visualize the problem: What edges would you remove from $G$ s.t. there are no more $k$-cliques?
Does this help? Or do you need more hint?