Extremal Graph

A two-coloring of a Complete Graph $K_n$ of $n$ nodes which contains exactly the number $N\equiv (R+B)_{\rm min}$ of Monochromatic Forced Triangles and no more (i.e., a minimum of $R+B$ where $R$ and $B$ are the numbers of red and blue Triangles). Goodman (1959) showed that for an extremal graph,

$$N(n)=\cases{ {\textstyle{1\over 3}} m(m-1)(m-2) & for $n=2m... ...$\cr {\textstyle{1\over 3}} 2m(m+1)(4m-1) & for $n=4m+3$.\cr}$$

This is sometimes known as Goodman's Formula. Schwenk (1972) rewrote it in the form

$$N(n)={n\choose 3}-\left\lfloor{{\textstyle{1\over 2}}n\left\... ...r{{\textstyle{1\over 4}}(n-1)^2}\right\rfloor }\right\rfloor ,$$

sometimes known as Schwenk's Formula, where $\left\lfloor{x}\right\rfloor$ is the Floor Function. The first few values of $N(n)$ for $n=1$, 2, ... are 0, 0, 0, 0, 0, 2, 4, 8, 12, 20, 28, 40, 52, 70, 88, ... (Sloane's A014557).

See also Bichromatic Graph, Blue-Empty Graph, Goodman's Formula, Monochromatic Forced Triangle, Schwenk's Formula

References

Goodman, A. W. ``On Sets of Acquaintances and Strangers at Any Party.'' Amer. Math. Monthly 66, 778-783, 1959.

Schwenk, A. J. ``Acquaintance Party Problem.'' Amer. Math. Monthly 79, 1113-1117, 1972.

Sloane, N. J. A. Sequence A014557 in ``The On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html.