Extremal Graph

In general, an extremal graph is the largest graph of order n which does not contain a given graph G as a subgraph (Skiena 1990, p. 143). Turán studied extremal graphs that do not contain a complete graph K_p as a subgraph.

One much-studied type of extremal graph is a two-coloring of a complete graph K_n of n nodes which contains exactly the number N=(R+B)_(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 of this type,

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

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

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

sometimes known as Schwenk's formula, where |_x_| 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, ... (OEIS A014557).

See also

Bichromatic Graph, Blue-Empty Graph, Extremal Graph Theory, Goodman's Formula, Monochromatic Forced Triangle, Schwenk's Formula, Turán Graph

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.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 143, 1990.Sloane, N. J. A. Sequence A014557 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Extremal Graph

Cite this as:

Weisstein, Eric W. "Extremal Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications