The Erd\H{o}s bipartification conjecture is true in the special case of Andr\'asfai graphs

Let the Andr'{a}sfai graph ${\mathrm{A}\mathrm{n}\mathrm{d}}_k$ be defined as the graph with vertex set $\{v_0,v_1,\mathrm{.}\mathrm{.}\mathrm{.}c,v_{3k-2}\}$ and two vertices $v_i$ and $v_j$ being adjacent iff $\mathrm{\mid }i-j\mathrm{\mid }\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}3$. The graphs ${\mathrm{A}\mathrm{n}\mathrm{d}}_k$ are maximal triangle-free and play a role in characterizing triangle-free graphs with large minimum degree as homomorphic preimages. A minimal bipartification of a graph $G$ is defined as a set of edges $F\subset E(G)$ having the property that the graph $(V(G),E(G)\mathrm{\backslash }F)$ is bipartite and for every $e\in F$ the graph $(V(G),E(G)\mathrm{\backslash }(F\mathrm{\backslash }e))$ is not bipartite. In this note it is shown that there is a minimal bipartification $F_k$ of ${\mathrm{A}\mathrm{n}\mathrm{d}}_k$ which consists of exactly $\lfloor \frac{k^2}{4}\rfloor$ edges. This equals $\lfloor 1\mathrm{/}36(\mathrm{\mid }{\mathrm{A}\mathrm{n}\mathrm{d}}_k\mathrm{\mid }+1{)}^2\rfloor$, where $\mathrm{\mid }\cdot \mathrm{\mid }$ denotes the number of vertices of a graph. For all $k$ this is consistent with a conjecture of Paul Erd\H{o}s that every triangle-free graph $G$ can be made bipartite by deleting at most $1\mathrm{/}25\mathrm{\mid }G{\mathrm{\mid }}^2$ edges. Bipartifications like $F_k$ may be useful for proving that arbitrary homomorphic preimages of an Andr'{a}sfai graph can be made bipartite by deleting at most $1\mathrm{/}25\mathrm{\mid }G{\mathrm{\mid }}^2$ edges.