Let the Andr\'{ a}sfai graph $\mathrm{ And}_k$ be defined as the graph with vertex set $\{ v_0,v_1,...c, v_{ 3k-2}\}$ and two vertices $v_i$ and $v_j$ being adjacent iff $|i-j| \equiv 1\mod 3$. The graphs $\mathrm{ And}_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)\backslash F)$ is bipartite and for every $e \in F$ the graph $(V(G), E(G)\backslash (F\backslash e))$ is not bipartite. In this note it is shown that there is a minimal bipartification $F_k$ of $\mathrm{ And}_k$ which consists of exactly $\lfloor\frac{ k^2}{ 4}\rfloor$ edges. This equals $\lfloor{ 1/36}\bigl(|\mathrm{ And}_k|+1\bigr)^2\rfloor$, where $|\cdot|$ 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/25} |G|^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/25} |G|^2$ edges.
Categories: math.CO