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,

 R+B={1/3m(m-1)(m-2)   for n=2m; 2/3m(m-1)(4m+1)   for n=4m+1; 2/3m(m+1)(4m-1)   for n=4m+3.

Schwenk (1972) rewrote the equation in the form

 R+B=(n; 3)-|_1/2n|_1/4(n-1)^2_|_|,

where (n; k) is a binomial coefficient and |_x_| is the floor function.

See also

Blue-Empty Graph, Extremal Graph, Monochromatic Forced Triangle

Explore with Wolfram|Alpha


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.

Referenced on Wolfram|Alpha

Goodman's Formula

Cite this as:

Weisstein, Eric W. "Goodman's Formula." From MathWorld--A Wolfram Web Resource.

Subject classifications