If we have a graph with 6 vertices, what is the minimal amount of edges needed, $k_6$, and how should they be put in the graph, in such manner that if I choose any 3 vertices of the graph at least two of them are certainly connected by an edge?
My guess is that 6 edges are needed forming two disconected triangles, but I am not sure how to prove that this is the minimal number. This is clearly the minimal number if the graph has two disconnected components, but how can I be sure that it is impossible to do with a smallest number of edges if the graph is connected?
And while we are at it, how could one attack the problem with $n$ vertices? that is how to find $k_n$? clearly $k_3 =1, k_4=2$