We can translate the problem in graph theoretical terms. We have $G$ a graph without $K_3$'s, and with at least one cycle of odd length (larger than $3$). Now, we add edges until we can't add anymore edges, without creating a $K_3$ (we will always have an odd cycle, because adding edges to a non bipartite graph can't make it bipartite) (maybe we won't add any edge at all). If we manage to prove the problem for this new graph $G'$, the degree of the vertex found in $G'$ would be larger than (or equal) to the degree of the same vertex in $G$. Now, the key claim of the proof: Claim: We have a cycle of length $5$ in $G'$. Proof: Suppose this is not the case, then take the cycle with minimal odd length, suppose it has $2k+1$ edges with $k \ge 3$. Denote this cycle $A_1-A_2-\cdots -A_{2k+1}$. $A_1$ and $A_4$ are not connected, otherwise $A_1-A_4-A_5-\cdots -A_{2k+1}$ has lenth $2k-1$, impossible. Now, we have a vertex, say $K$ with $K$ connected to both $A_1$ and $A_4$ (otherwise, adding an edge between $A_1$ and $A_4$ doesn't create a $K_3$), so $A_1-A_2-A_3-A_4-K$ is a cycle of length $5<2k+1$, impossible. Now, denote the vertices of our $5$-cycle $B_1,\ldots,B_5$, with $b_i$ the degree of $B_i$. Because of obvious reasons, this cycle is an induced cycle ($B_i$ is connected to $B_j$ if and only if $|i-j|\equiv 1(mod 5)$). Take $X \neq B_i$ a vertex of our graph. $X$ can have at most $2$ neighbors in our cycle, so by a double counting argument $b_1+b_2+\cdots +b_5\le 2n-10+ 10$, so we have a $b_i \leq \frac{2}{5}n$, and we are done.

MariusBocanu wrote: We have $G$ a graph without $K_3$'s, and with at least one cycle of odd length (larger than $3$). A little cryptic. In fact the second requirement translates in $G$ not being bipartite (as hinted at further on in the proof), and so the solver uses the known result that a graph is bipartite if and only if all its cycles are of even length, thus inferring the existence of an odd cycle of length larger than $3$. Nice proof otherwise (by saturating the graph). Let us also notice that the bound $\dfrac {2}{5}n$ cannot be improved, since for $G=C_5$ we get precisely that.