1
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ You are correct, you need at least $6$ edges, and the only graph with six vertices is the one that you proposed. $\endgroup$ – Jorge Fernández Hidalgo Mar 17 '15 at 0:24
2
$\begingroup$

The graph with the least edges that does not have an independent set of $r+1$ vertices is always the complement of the Turan graph $T(n,r)$ and it is in fact the only graph with that number of edges satisfying that property.

It should be clear that a graph $G$ without $r$ independent vertices satisfies that it's complement contains no $K_r$ as a subgraph and vice-versa. So you need to find the graph on $n$ vertices with the most number of edges that does not have a $K_r$ and take it's complement, but by Turan's theorem that graph is the Turan graph. So what we want is the complement of the Turan graph.

The complement of the Turan graph $T(n,r+1)$ is in general a the graph on $n$ vertices that has $r$ components, where each component is complete and where the differences between the sizes of components is at most one. So in your case the graph is composed of two $K_3$'s, in other words two disjoint triangles.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.