Prove that : $f(n) \le \frac{1}{4}(n-1)^2+1 $ Let $f(n)$ denote the largest number of edges on $n$ vertices among triangle-free graphs that are non-bipartite . For all $n \geq 5 $ prove that:

*

*$f(n) \le \frac{1}{4} (n-1)^2+1$

*Let's construct a graph where $" = "$ occurs.

It's easy to see that $Mantel's $problem gives us a structured result similar to mine (though I don't know if it helps)
$Mantel$ Problem : Deduce from the proof of Mantel theorem the following strengthening of the assertion. Let G be a triangle-free graph of order n. Then $ e(G)≤n^2/4$
According to the problem , the given graph cannot be divided into non - bipartite graph   , so it will have an odd degree cycle .
I am thinking of dividing the vertices of the graph into 2 parts, one part contains the vertices in that cycle, the other part contains the remaining vertices. But my work has not progressed at all.
 A: 
Let $G$ be a non-bipartite graph of order $n$ without triangles. Then
$|E(G)|\leq\frac{(n-1)^2}{4}+1$.

Proof. Since the graph does not contain triangles, for any edge $uv$ we have $\deg(u)+\deg(v)\leq n$.
The following three cases are possible.
(1) There is a pair of adjacent vertices $u,v$ for which
$\operatorname{deg}u+\operatorname{deg}v=n$.
(2) There is a pair of adjacent vertices $u,v$ for which
$\operatorname{deg}u+\operatorname{deg}v=n-1$.
(3) For any adjacent vertices $u$ and $v$ the inequality
$\operatorname{deg}u+\operatorname{deg}v\leq n-2$ holds.
Consider each case.
(1) If $\operatorname{deg}u+\operatorname{deg}v=n$,
then our graph is bipartite with parts $N(u)$ and $N(v)$,
where $N(x)$ are all neighbors of $x$.
(2) Let $\operatorname{deg}u+\operatorname{deg}v=n-1$ and $w\notin N(u)\cup N(v)$.
If $N(w)\cap N(u)=\varnothing$ or
$N(w)\cap N(v)=\varnothing$, then the graph is bipartite.
If $k=|N(w)\cap N(u)|>0$ and $l=|N(w)\cap N(v)|>0$ and $d=\operatorname{deg}u$,
then since the graph without triangles
$$
|E(G)|\leq \operatorname{deg}u\cdot \operatorname{deg}v+k+l-kl\leq
\operatorname{deg}u\cdot \operatorname{deg}v+1=(n-1)d-d^2+1=
$$
$$
-\left(d-\frac{n-1}{2}\right)^2+\frac{(n-1)^2}{4}+1\leq\frac{(n-1)^2}{4}+1.
$$
(3) If
$\operatorname{deg}u+\operatorname{deg}v\leq n-2$ for any adjacent vertices $u$ and $v$, then
$$
(n-2)|E(G)|\geq\sum_{uv\in E(G)}(\operatorname{deg}u+\operatorname{deg}v)=
\sum_{u\in V(G)}(\operatorname{deg}u)^2\geq
$$
$$
\frac{1}{n}\left(\sum_{u\in V(G)}\operatorname{deg}u\right)^2=\frac{4|E(G)|^2}{n}.
$$
So
$$
|E(G)|\leq\frac{n(n-2)}{4}<\frac{(n-1)^2}{4}.
$$
Addendum (in response to @ZFR's 20.07.2022 questions).
If $uv$ is an edge, $\deg(u)+deg(v)=n-1$, $N(u)\cap N(v)=\varnothing$, $w\notin N(u)\cup N(v)$, and for example $N(w)\cap N(u)=\varnothing$, then the graph is bipartite and its parts are $N(v)$ and $N(u)\cup\{w\}$.
Why does the inequality
$$
|E(G)|\leq\deg(u)\cdot\deg(v)+k+l-kl
$$
hold?
In a graph $G$ there can be only edges connecting vertices of sets $N(u)$ and $N(v)$ except for edges connecting vertices $N(w)\cap N(u)$ and $N(w)\cap N(v)$ (such edges cannot exceed $\deg(u)\cdot\deg(v)-kl$), edges connecting the vertex $w$ with some vertices of $N(u)$ and $N(v)$ (there are exactly $k+l$).
The inequality $k+l-kl\leq1$ follows from the fact that $(k-1)(l-1)\geq0$.
A: The following solutions are adapted from some class notes by Jonathan Rollin.
Let $G$ be a graph witn $n$ vertices that is triangle free and not bipartite.  So $G$ contains a cycle of odd length.  We are first asked to show that the number of edges is at most $(n-1)^2/4 + 1$.
If $n=5$, then the graph must be a cycle of length $5$, and the inequality is sharp: $(5-1)^2/4 + 1 = 5$ edges.
Otherwise $n\ge 6$, and we proceed by induction.  Let $C$ be a shortest odd cycle contained in $G$, say of length $k$.  Since $C$ is the shortest odd cycle, the graph $G$ does not contain any "chord" edge of $C$ (because that would create a strictly shorter odd cycle on one "side" or the other of that chord).
Let $X$ be the set of vertices in $G$ but not in $C$. Claim: Each vertex $v\in X$ has at most two neighbors in $C$.  Suppose for contradiction that $v\in X$ has three or more neighbors in $C$.  Three such neighbors would split the cycle $C$ into three paths, each of length greater than one (since $G$ is triangle free).  Those three paths combined have all $k$ edges of $C$, and since $k$ is odd, at least one of those paths contains an odd number of edges less than $k-2$.  But then that path together with the two edges joining $v\in X$ would give a shorter odd length cycle than $C$.  This contradiction establishes the claim.
Now we can upper bound the total number of edges in $G$.  First by Mantel's Thm. the number of edges between the vertices in $X$ is at most $\lfloor |X|^2/4 \rfloor$ as this subgraph of $G$ is also triangle free.  Second the number of edges between vertices in $X$ and in $C$ is at most $2|X|$ by the preceding paragraph's claim.  Finally, by the observation that $G$ contains no chords on $C$, the number of edges between vertices of $C$ is exactly $k$, the length of $C$.
Note that $|X| = n-k$ and $k\ge 5$, so $n-k \le n-5$. Thus the number of edges in $G$ is at most:
$$ \begin{aligned} \lfloor \frac{(n-k)^2}{4} \rfloor + 2(n-k) + k &\le \frac{1}{4}\left((n-5)^2 + 4(n-5) + 4(n-1)\right) + 1 \\ &= \frac{1}{4}(n-1)^2 + 1 \end{aligned}$$
For the second part of the problem one can show equality is attained whenever $n\ge 5$ is odd.  Suppose $n = 2t+1$, and consider the complete bipartite graph $K_{t,t}$ having two equal size parts.  Remove an edge $uv$ and add a new vertex $w$ with edges $uw$ and $vw$.  That graph has $n$ vertices and $(n-1)^2/4 + 1$ edges (since we removed one, then added two edges).  Finally the Reader should verify that it is not bipartite and is triangle free.
