EWD1302

Once more bichrome triangles in complete graphs

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 n−1 edges that share an end point form at most k∙(k−1) mixed Vs. Hence there are at most n∙k∙(k−1) mixed Vs, and

(0)	nbt ≤ k2∙(k−1)     .

n = 2k + 1  .  The n−1 edges that share an end point form at most k² mixed Vs. Hence there are at most k²∙n mixed Vs and

(1)	nbt ≤ k2∙(2k+1)/2     .

(Note that the right-hand 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 A-nodes and k B-nodes, colour the AA- and the BB-edges red and the AB-edges blue. Then each node has a red degree equal to k−1 and a blue degree equal to k, which, n−1 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 (k−1, k+1); this corresponds to the situations in which the right-hand side of (1) is not an integer.