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 F n ⊂ [ 0 , ( n 3 ) ] of possible number of frustrated triangles f ( G ) in a graph G on n vertices. We prove that about two thirds of the numbers in [ 0 , n 3 / 2 ] cannot appear in F n , and we characterise the graphs G with f ( G ) ∈ [ 0 , n 3 / 2 ] . More precisely, our main result is that, for each n ≥ 3 , F n contains two interlacing sequences 0 = a 0 ≤ b 0 ≤ a 1 ≤ b 1 ≤ ⋯ ≤ a m ≤ b m ∼ n 3 / 2 such that F n ∩ ( b t , a t + 1 ) = 0̸ for all t , where the gaps are | b t − a t + 1 | = ( n − 2 ) − t ( t + 1 ) and | a t − b t | = t ( t − 1 ) . Moreover, f ( G ) ∈ [ a t , b t ] if and only if G can be obtained from a complete bipartite graph by flipping exactly t edges/nonedges. On the other hand, we show, for all n sufficiently large, that if m ∈ [ f ( n ) , ( n 3 ) − f ( n ) ] , then m ∈ F n where f ( n ) is asymptotically best possible with f ( n ) ∼ n 3 / 2 for n even and f ( n ) ∼ 2 n 3 / 2 for n odd. Furthermore, we determine the graphs with the minimum number of frustrated triangles amongst those with n vertices and e ≤ n 2 / 4 edges. [ABSTRACT FROM AUTHOR]