We consider the bichrome triangles in a complete \(n\)graph of which each of its edges is either red or blue. Each bichrome triangle has 2 "mixed Vs," where a mixed V is a pair of edges with different colours and a shared end point, while a monochrome triangle has no mixed Vs. Thus we can find an upper bound for \(nbt\), i.e. the number of bichrome triangles, by halving an upper bound for the number of mixed Vs. We distinguish even and odd \(n\).
\(n = 2k\) . The \(n1\) edges that share an end point form at most \(k\cdot (k1)\) mixed Vs. Hence there are at most \(n\cdot k\cdot(k1)\) mixed Vs, and
(0) 
\[ \begin{equation} nbt \leq k^{2}\cdot (k1) \end{equation}\]

. 
\(n = 2k+1\) . The \(n1\) edges that share an end point form at most \(k^{2}\) mixed Vs. Hence there are at most \(k^{2}\cdot n\) mixed Vs and
(1) 
\[ \begin{equation} nbt \leq k^{2}\cdot (2k+1)/2 \end{equation}\]

. 
(Note that the righthand side need not be integer.)
The rest of this note is devoted to the question whether these upper bounds are as low as possible. The answer will turn out to be affirmative. This will be demonstrated by constructing for arbitrary \(n\) a graph such that for each node red and blue degree are as equal as possible, i.e. the situation from which the upper bounds (0) and (1) are derived [the red/blue degree of a node is the number of red/blue edges sharing that node as an endpoint.] We deal with even and odd \(n\) separately.
\(n = 2k\) . Partition the \(n\) nodes into \(k\) Anodes and \(k\) Bnodes, colour the AA and the BBedges red and the ABedges blue. Then each node has a red degree equal to \(k1\) and a blue degree equal to \(k\), which, \(n1\) being odd, is as equal as you can get them.
\(n = 2k+1\) This case is slightly more complicated because the situation that in each node the degrees are both equal to \(k\) can only be obtained for even \(k\); for uneven \(k\) we must admit 1 node with degrees \((k1, k+1)\); this corresponds to the situations in which the righthand side of (1) is not an integer.
As before we partition the \(n\) nodes, but this time into \(n+1\) Anodes and \(n\) Bnodes. Were we to colour them as before, each Anode would have degrees \((k,k)\) as desired, but each Bnode would have degrees \((k1, k+1)\). To remedy the situation, consider the following transformation:
A  —  A  A  —  A  
    →      
B  B  B  B 
While it leaves the degrees of all Anodes unchanged, it can be used to change at 2 Bnodes degrees \((k1, k+1)\) into \((k,k)\), as desired. With \(k=2\cdot h\) or \(k=2\cdot h+1\) , we can apply this transformation on \(h\) disjoint pairs of Bnodes (and \(h\) distinct, and hence initially red, AAedges).
Note For odd \(k\), a node with degrees differing from \((k,k)\) is unavoidable because the sum of the red/blue degrees is even.
(End of Note.)
Prof. Dr. Edsger W. Dijkstra
Department of Computer Sciences
The University of Texas at Austin
Austin, TX 787121188
USA
Transcribed by Jordan Olsommer; MathJax added by H. Richards.
Last revised