If $G$ is a triangle-free and $\delta(G)$ is large, then $G$ is bipartite graph

Question

Show that every $n$-vertex triangle-free graph with minimum degree greater than $2n/5$ is bipartite.

First of all this result is vacuously true for $n=1,3,5$. For $n=2$ and $n=4$, it is trivially true since the desired graphs are $K_2$ and $K_{2,2}$.

We assume that $n\geq 6$ and $V(G)=\{v_1,\dots,v_n\}$. Since $\deg(v_1)>2n/5$, then take $v_2\in N(v_1)$ and consider $N(v_2)$ also.

It is easy to see that $N(v_1)$ and $N(v_2)$ are disjoint and independent sets. Moreover, $|V(G)\setminus (N(v_1)\sqcup N(v_2))|<n/5$.

1. Consider the most trivial case, when $V(G)\setminus (N(v_1)\sqcup N(v_2))=\varnothing$. Hence $V(G)=N(v_1)\sqcup N(v_2)$ and $G$ is a bipartite graph with vertex sets $N(v_1)$ and $N(v_2)$ , i.e. $G=G[N(v_1),N(v_2)]$.

2. If $|V(G)\setminus (N(v_1)\sqcup N(v_2))|=1$, then $V(G)= N(v_1)\sqcup N(v_2)\sqcup \{w\}$. If $N(w)\cap N(v_1)=\varnothing$ or $N(w)\cap N(v_2)=\varnothing$, then $G$ is bipartite graph. Indeed, assume WLOG that $N(w)\cap N(v_1)=\varnothing$, then $G$ is a bipartite with vertex sets $N(v_1)\sqcup \{w\}$ and $N(v_2)$.

Question 1. What if $|N(w)\cap N(v_1)|=k>0$ and $|N(w)\cap N(v_2)|=\ell>0$? I sketched a picture and I see that $G$ is not bipartite in this case. I was wondering how to prove it rigorously?

Question 2. I was wondering is it possible to solve the problem with that approach? It seems a bit difficult to me but I did not checked the details since I stucked in question 1.

Answer 1

This is not really answering your questions, but I'd like to suggest a possibly less complicated way of solving this exercise.

Let $G$ be a triangle-free simple graph of order $n$ with $\delta(G)\gt2n/5$, and assume for a contradiction that $G$ is not bipartite. Let $k$ be the length of a shortest odd cycle in $G$ (so $k\ge5$) and let $C$ be a cycle in $G$ of length $k$. Let $M=V(G)\setminus V(C)$ and $m=|M|$.

Since a vertex $v\in V(C)$ is joined to at most $2/5$ of the vertices in $C$, it must be joined to more than $2/5$ of the vertices in $M$, i.e., $|N(v)\cap M|\gt2m/5$. Hence, if $x$ is the number of edges between $V(C)$ and $M$, then $x\gt2mk/5\ge2m$. It follows that some vertex $w$ in $M$ must have at least $3$ neighbors in $C$. But now we can use $w$ to create an odd cycle of length less than $k$.