triangle free and connected graph

Question

Let G be a connected and triangle-free graph with 82 vertices, Prove that alpha(G)>=10 Where alpha(G) is the maximal independent set of G.

I've shown that if the maximal independent set is on 9 vertices , Then any other vertex we add to this set, it will be connected to at least one of them. Then if we part the 73 vertices left to which one they're connected (if it is two different vertices choose one randomally) We get one vertex of the independent set connected to atleast 9. If more then 9 we can find a triangle, If 9 they create a new anti clique of 9 vertices. I don't know how to continue from here.

Thank you.

Answer 1

I thought this would be easy but it turned out to be pretty elaborate. There might be something more elegant.

As you deduced, there has to be a vertex $x$ of degree 9. Note that this is the maximum degree of any vertex, as you probably know from the fact that all vertices in the neighborhood of a given vertex form an anticlique.

Denote the neighborhood $N(x)$ of $x$ by $X$, and let $X' = N(X) \setminus \{x\}$ (the neighbors of vertices of $X$ except $x$). Then let $X'' = N(X') \setminus X$. So $X''$ are the "neighbors of neighbors" of $X$. If $X''$ is not empty, then you can find an independent set of size 10 by taking the 9 vertices of $X$, plus any vertex from $X''$, as $X$ and $X''$ share no edge by construction.

Thus $x, X$ and $X'$ contain all the 82 vertices. This implies that $|X'| = 82 - 10 = 72$, which is only possible if each of the 9 vertices of $X$ has 8 distinct neighbors in $X'$. So $X'$ consists of 9 independent sets of 8 vertices. Call these sets $S$.

Now, let $G[X']$ be the graph induced by $X'$. If $G[X']$ has an independent set of size 9, then we can add $x$ to this set to get $\alpha(G) = 10$. Take a vertex $v$ of $G[X']$. There are 8 independent sets of $S$ that $v$ isn't in. Take one of these and call it $S_i$. If $v$ has no neighbors in $S_i$, then $S_i + v + x$ gives $\alpha(G) = 10$. So $v$ has an edge going into each 8 sets of $S$ it's not in. This is true for any $v$, for $G[X']$ is 8-regular (and $G$ is 9-regular, but who cares at that point !).

Now we apply the same construction as before to find that $\alpha(G[X']) \geq 9$. Take some $y \in V(G[X'])$, and as we did let $Y = N(y), Y' = N(Y) \setminus \{y\}$ and $Y'' = N(Y') \setminus Y$. We have $|Y| = 8$ and $|Y'| \leq 8 \times 7 = 56$. Since this time, $G[X']$ has 72 vertices, $Y''$ can't be empty, and we find an independent set of size 9 by taking $Y$ and any vertex of $Y''$.

Answer 2

I just wanted to point out that we don't actually need $83$ vertices, any number of vertices greater than $R(10,3)$ will do, and in particular we have the upper bound for $R(10,3)$ of 42.

Answer 3

There is another solution for this kind of exercises:
We can use Brook's theorm- since the graph isn't clique and the graph isn't an odd cycle, $\chi(G) \leq \Delta(G)$.
Now there are two cases:
Case 1: there is a vertex $x$ , s.t , $deg(x)> 9$ : In that case, since there are no triangulars, the neighbers of $x$ form an indep set of order $\geq 10$.
Case 2: $\Delta(G) \leq 9$: Using Brook's thm, we can colour G with 9 colours. By piegonhole theorm, there is colour class with 10 vertices- hence an independent set with the demanded order.