Frustrated triangles

A triple of vertices in a graph is a frustrated triangle   if it induces an odd number of edges. We study the set Fn⊂[0,(n3)] of possible number of frustrated triangles f(G)f(G) in a graph GG on nn vertices. We prove that about two thirds of the numbers in [0,n3/2][0,n3/2] cannot appear in FnFn, and we characterise the graphs GG with f(G)∈[0,n3/2]f(G)∈[0,n3/2]. More precisely, our main result is that, for each n≥3n≥3, FnFn contains two interlacing sequences 0=a0≤b0≤a1≤b1≤⋯≤am≤bm∼n3/20=a0≤b0≤a1≤b1≤⋯≤am≤bm∼n3/2 such that Fn∩(bt,at+1)=0̸Fn∩(bt,at+1)=0̸ for all tt, where the gaps are |bt−at+1|=(n−2)−t(t+1)|bt−at+1|=(n−2)−t(t+1) and |at−bt|=t(t−1)|at−bt|=t(t−1). Moreover, f(G)∈[at,bt]f(G)∈[at,bt] if and only if GG can be obtained from a complete bipartite graph by flipping exactly tt edges/nonedges. On the other hand, we show, for all nn sufficiently large, that if m∈[f(n),(n3)−f(n)], then m∈Fnm∈Fn where f(n)f(n) is asymptotically best possible with f(n)∼n3/2f(n)∼n3/2 for nn even and f(n)∼2n3/2 for nn odd. Furthermore, we determine the graphs with the minimum number of frustrated triangles amongst those with nn vertices and e≤n2/4e≤n2/4 edges.