Turan's theorem for connected graphs?

Question

Using a small modification to Turáns theorem we can find the minimum amount of edges a graph $G$ on $n$ vertices must have so it does not have an independent set of size $k$. Is there a similar result if we add the restriction that $G$ is a connected graph?

Answer 1

Just a partial answer, expanding Tony's:

The statement is true for $n=2k$ (i.e. you need exactly $(2k-1)$ edges to avoid an independent set of size $k+1$ in a connected graph), and the extremal graphs are exactly the trees with a perfect matching.

Proof: Clearly, you need $2k-1$ edges to make it connected. And $2k-1$ are sufficient, take any tree without an independence set of size $k+1$ (a path would do).

It remains the classification. Clearly we only need to consider trees.

If a tree on $2k$ vertices has no independent set of size $k+1$, then it has a perfect matching: proof by induction on $k$. $k=1$ is trivial. For $k>1$, consider a non-leaf $v$. If we delete $v$, the remaining forest has exactly one odd component $T_v$, all other components are even. Otherwise, pick the bigger part in the bipartition of each component, and you end up with an independent set of size $k+1$. By the same reason, each component of size $2k'$ has independence number $k'$, and thus by induction a perfect matching. It remains to consider $T_v+ v$. If this tree had an independent set of size larger then half, we could combine this with the parts in the other components not incident to $v$ to create an independence set of size $k+1$, again a contradiction. So, again by induction, $T_v+v$ has a perfect matching.

If a tree on $2k$ vertices has a perfect matching, then it has no independent set of size $k+1$: This follows trivially from PHP.

Answer 2

This is not an answer, but it became a bit too long for a comment.

If we let $\tau(n,k)$ be the number of edges in the complement of the Turan graph $T(n,k)$, then the minimum number of edges a connected graph with no independent set of size $k+1$ is probably $\tau(n,k)+k-1$. Note that it is at least $\tau(n,k)+1$ by Turan's theorem (it cannot be exactly $\tau(n,k)$ since $\overline{T(n,k)}$ is the unique graph on $n$ vertices with $\tau(n,k)$ edges and no independent set of size $k+1$). On the other hand, it is at most $\tau(n,k)+k-1$ since we can add $k-1$ edges to the complement of $T(n,k)$ to make it connected.

Edit. Note that the bound is tight for $n=2k$, and all the extremal examples do come from Turan's theorem. See Flo Pfender's answer, which corrects an error in a previous version of this answer.

Answer 3

First, tthere are other extremal examples than the complement of the Turan graph for $n = 3k-4$. The $3k-4$ example is given by the following. There is also an easy construction that shows that the guess of Turan theorem plus $k-2$ is not enough for $n = 2k-1$.

Let $G$ be a $K_r$ free graph who has a connected complement. What is the maximal number of edges $G$ can have?

I will prove for $n \geq Cr^2$ for a small constant $C$ that the Turan graph minus $r-2$ edges is the best (and only) possible.

The key observation for the other statement is that if a graph is $K_r$ free and has close to the number of edges in the Turan graph, then the graph is close to an $r-1$ partite graph (and indeed if close is replaced by very close, one can replace it is a $r-1$ partite graph). At least two of the proofs of Turan's theorem in this paper generalize to prove such a statement (the second and third) for large graphs, though it is not obvious (especially how the second generalizes). Erdos-Simonivits is related, but the bound is too weak for your question. I will outline how to extend Erdos' proof which is unpublished work of Furedi, though can be found in a presentation of his here.

He shows the following in a very elegant manner.

Claim: Let $G$ be a graph such that (i) $G$ is $K_r$ free (ii) $e(G) \geq |T(n,r-1)| - t$ Then one can remove at most $t$ edges from $G$ to create a $r-1$ partite graph.

(Pf) Let $x_1 \in V(G)$ such that the degree of $x_1$ is chosen maximally. Let $V_1$ be all the non-neighbors of $G$. Similarly, let $x_2$ be chosen such that the degree of $x_2$ in the induced subgraph of $G \setminus V_1$ is maximal. Let $V_2$ be all of the vertices in $G \setminus V_1$ that are not adjacent to $x_2$. Repeat this process (chossing $x_j$ so that the degree in the induced subgraph $G \setminus (V_1 \cup \ldots \cup V_{j-1})$ is maximal) to eventually get vertices $x_1 , \ldots , x_{r-2}$ and vertex sets $V_1 , \ldots , V_{r-1}$. Note that since $G$ is $K_r$ free, $V_{r-1}$ is an independent set. Let $G_1$ be the spanning subgraph containing exactly the edges. Then $$e(G) \leq \sum_{i=1}^{r-2} d_{V_{i+1} \cup \ldots \cup V_{r-1}}(x_i) |V_i|.$$ But in this counting, we counted each edge inside $G_1$ twice. Thus $$e(G) \leq \sum_{i=1}^{r-2} d_{V_{i+1} \cup \ldots \cup V_{r-1}}(x_i) |V_i| - e(G_1) \leq T(n,r-1) - e(G_1),$$ and the result follows by the assumption.

This result quickly implies the following result.

Claim: Let $G$ be a graph such that (i) $G$ is $K_r$ free (ii) $e(G) \geq |T(n,r-1)| - (r-2)$ (iii) $G$ contains at least $Cr^2$ vertices for some computable (small) constant $C$ Then $G$ is a $r-1$ partite graph.

(Sketch of Proof, which can be found here) Let $G_0$ be the maximal spanning $r-1$ partite graph and $G_1 = (V(G) , E(G) \setminus E(G_0))$. By the previous claim $|E_(G_1)| \leq r-2$. If one of the color classes of $G_0$ is smaller than say $\frac{n}{2(r-1)}$, then this contradicts $(ii)$ and $(iii)$. If there is an edge in $G_1$, then using the fact that $G$ is $K_r$ free, one can show that, without much difficulty, that $|E(G_0)| \leq |T(n,r-1)| - \frac{n}{2(r-1)}$. This is a contradiction to $(ii)$ and $(iii)$.

This stability theorem immediately implies that the Turan graph minus $r-2$ edges is the best (and only) possible construction for a graph with maximum number of edges that is $K_r$ free and who has a connected complement.