info prev up next book cdrom email home

Goodman's Formula

A two-coloring of a Complete Graph $K_n$ of $n$ nodes which contains exactly the number of Monochromatic Forced Triangles and no more (i.e., a minimum of $R+B$ where $R$ and $B$ are the number of red and blue Triangles) is called an Extremal Graph. Goodman (1959) showed that for an extremal graph,

$\displaystyle R+B$ $\textstyle =$ $\displaystyle \left\{\begin{array}{ll} {\textstyle{1\over 3}} m(m-1)(m-2) & \mb...
...\  {\textstyle{2\over 3}} m(m+1)(4m-1) & \mbox{for $n=4m+3$.}\end{array}\right.$  

Schwenk (1972) rewrote the equation in the form

R+B={n\choose 3}-\left\lfloor{{\textstyle{1\over 2}}n\left\l...
...r{{\textstyle{1\over 4}}(n-1)^2}\right\rfloor }\right\rfloor ,

where ${n\choose k}$ is a Binomial Coefficient and $\left\lfloor{x}\right\rfloor $ is the Floor Function.

See also Blue-Empty Graph, Extremal Graph, Monochromatic Forced Triangle


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.

© 1996-9 Eric W. Weisstein