Goodman's theorem

In graph theory, Goodman's theorem gives the exact minimum number of monochromatic triangles in a two-coloring of the edges of a complete graph. If the edges of $K_{n}$ are colored red or blue, the minimum depends on $n$ modulo four. A. W. Goodman published the result in 1959, phrasing the two colors as pairs of acquaintances and strangers at a party. Forms of the result are also known as Goodman's formula.

The proof counts pairs of differently colored edges incident with each vertex and reduces the lower bound to a degree calculation. Dividing the exact minimum by the total number of triangles gives a limiting proportion of $1/4$, the same as the expected monochromatic proportion in a uniformly random red–blue coloring. In Ramsey theory this says that $K_{3}$ is a common graph. Goodman also proved a related inequality between edge and triangle homomorphism densities. Later work determined the three-color minimum for all sufficiently large complete graphs and the four-color asymptotic minimum.

Statement

Let $M(K_{3},n)$ be the minimum number of unlabeled monochromatic copies of $K_{3}$ among all red–blue edge-colorings of $K_{n}$. Goodman's theorem states that

$$M(K_{3},n)={\begin{cases}\displaystyle {\frac {n(n-2)(n-4)}{24}},&n{\text{ even}},\\[6pt]\displaystyle {\frac {n(n-1)(n-5)}{24}},&n\equiv 1{\pmod {4}},\\[6pt]\displaystyle {\frac {(n+1)(n-3)(n-4)}{24}},&n\equiv 3{\pmod {4}}.\end{cases}}$$

Each of the three bounds is attainable. A. J. Schwenk later gave the equivalent single expression

$$M(K_{3},n)={n \choose 3}-\left\lfloor {\frac {n}{2}}\left\lfloor {\frac {(n-1)^{2}}{4}}\right\rfloor \right\rfloor .$$

The first nonzero value is $M(K_{3},6)=2$. Thus the theorem on friends and strangers, which guarantees a monochromatic triangle in every red–blue coloring of $K_{6}$, can in this case be strengthened to two monochromatic triangles.

As $n$ tends to infinity,

$${\frac {M(K_{3},n)}{n \choose 3}}\longrightarrow {\frac {1}{4}}.$$

A fixed triangle in a uniformly random red–blue edge-coloring is monochromatic with probability $2(1/2)^{3}=1/4$. The deterministic minimum therefore has the same limiting density as the random-coloring expectation.

Proof

For a vertex $v$, let $r_{v}$ and $b_{v}$ be its red and blue degrees. Then $r_{v}+b_{v}=n-1$. The product $r_{v}b_{v}$ counts unordered pairs of differently colored edges incident with $v$. Every nonmonochromatic triangle contributes such a pair at exactly two of its vertices, while a monochromatic triangle contributes none. If $N$ is the number of nonmonochromatic triangles, double counting gives

$$2N=\sum _{v}r_{v}b_{v}.$$

Consequently, if $T$ is the number of monochromatic triangles, then

$$T={n \choose 3}-{\frac {1}{2}}\sum _{v}r_{v}b_{v}={n \choose 3}-{\frac {1}{2}}\sum _{v}r_{v}(n-1-r_{v}).$$

The product is largest when the two degrees are as close as the integer and parity constraints permit. If $n=2m$, then $r_{v}b_{v}\leq m(m-1)$ for every vertex, and hence

$$T\geq {n \choose 3}-{\frac {n}{2}}m(m-1)={\frac {n(n-2)(n-4)}{24}}.$$

Now suppose $n$ is odd and put $q=(n-1)/2$. For each vertex,

$$r_{v}(n-1-r_{v})=q^{2}-(r_{v}-q)^{2}.$$

If $n\equiv 1{\pmod {4}}$, the pointwise bound $r_{v}b_{v}\leq q^{2}$ gives

$$T\geq {n \choose 3}-{\frac {nq^{2}}{2}}={\frac {n(n-1)(n-5)}{24}}.$$

If $n\equiv 3{\pmod {4}}$, then $q$ and $n$ are both odd. The red graph cannot have degree $q$ at every vertex, because its degree sum would be odd, contrary to the handshaking lemma. Thus $\sum _{v}(r_{v}-q)^{2}\geq 1$, so

$$T\geq {n \choose 3}-{\frac {nq^{2}-1}{2}}={\frac {(n+1)(n-3)(n-4)}{24}}.$$

These arguments establish the three lower bounds. Colorings attaining them exist in every case, so the bounds give the exact minimum. The floor functions in Schwenk's expression encode the same two integer restrictions: the largest value of a single product $r_{v}b_{v}$ and, when $n\equiv 3{\pmod {4}}$, the parity obstruction on the degree sum.

Graph and density formulations

A red–blue coloring of $K_{n}$ can be represented by a simple graph $G$, with the red edges taken as $E(G)$ and the blue edges as the edges of the complement graph ${\overline {G}}$. If $\tau (G)$ denotes the number of unlabeled triangles in $G$, the counting identity becomes

$$\tau (G)+\tau ({\overline {G}})={n \choose 3}-{\frac {1}{2}}\sum _{v\in V(G)}d_{G}(v){\bigl (}n-1-d_{G}(v){\bigr )}.$$

Thus the combined number of triangles in a graph and its complement is determined by the degree sequence. The lower-bound part of Goodman's theorem is therefore a degree optimization; the separate attainability statement ensures that the optimum degree patterns needed for the three congruence cases can be realized by colorings.

In graph-limit notation, the asymptotic two-color consequence is the graphon inequality

$$t(K_{3},W)+t(K_{3},1-W)\geq {\frac {1}{4}}.$$

Here $W$ and $1-W$ represent the two color classes, and $t(K_{3},W)$ is the triangle homomorphism density. The constant graphon $W=1/2$ attains equality. A different inequality attributed to Goodman, and also discussed under his name in the homomorphism-density setting, relates the triangle and edge densities of a single graphon:

$$t(K_{3},W)\geq t(K_{2},W){\bigl (}2t(K_{2},W)-1{\bigr )}.$$

The first inequality is the asymptotic form of the monochromatic-triangle problem; the second fixes one graphon and bounds its triangle density from its edge density.

Ramsey multiplicity and multicolor extensions

For a graph $H$ and a positive integer $k$, let $M_{k}(H,n)$ be the minimum number of monochromatic unlabeled copies of $H$ among all $k$-edge-colorings of $K_{n}$. Goodman's theorem gives $M_{2}(K_{3},n)$ exactly. Its limiting value of $1/4$ agrees with the random two-color benchmark, which is the statement that the triangle is a common graph.

Goodman considered the three-color analogue in 1985. He did not determine the minimum total number of monochromatic triangles, but obtained sharp bounds for related combinations of triangle types. In 2013, James Cummings, Daniel Král', Florian Pfender, Konrad Sperfeld, Andrew Treglown, and Michael Young determined the three-color minimum for all sufficiently large $n$. If $n=5m+r$ with $0\leq r\leq 4$, their result gives

$$M_{3}(K_{3},n)=r{m+1 \choose 3}+(5-r){m \choose 3}$$

for all sufficiently large $n$, and hence an asymptotic monochromatic-triangle density of $1/25$. Their proof combines a flag-algebra calculation with a probabilistic argument.

For four colors, Aldo Kiem, Sebastian Pokutta, and Christoph Spiegel proved in 2026 that the asymptotic minimum is $1/256$ of all triangles. They also showed that every sufficiently large extremal coloring is based on a blow-up of one of the two triangle-free three-colorings of $K_{16}$; their proof uses a flag-algebra formulation and stability arguments.

Bibliography

• Goodman, A. W. (1959). "On Sets of Acquaintances and Strangers at any Party". The American Mathematical Monthly. 66 (9): 778–783. doi:10.1080/00029890.1959.11989408. JSTOR 2310464.
• Schwenk, A. J. (1972). "Acquaintance Graph Party Problem". The American Mathematical Monthly. 79 (10): 1113–1117. doi:10.1080/00029890.1972.11993198.
• Goodman, A. W. (1985). "Triangles in a complete chromatic graph with three colors". Discrete Mathematics. 57 (3): 225–235. doi:10.1016/0012-365X(85)90175-X.
• Sane, S. S.; Wallis, W. D. (1988). "Monochromatic triangles in three colours". Bulletin of the Australian Mathematical Society. 37 (2): 197–212. doi:10.1017/S0004972700026733.
• Cummings, James; Král', Daniel; Pfender, Florian; Sperfeld, Konrad; Treglown, Andrew; Young, Michael (2013). "Monochromatic triangles in three-coloured graphs". Journal of Combinatorial Theory, Series B. 103 (4): 489–503. arXiv:1206.1987. doi:10.1016/j.jctb.2013.05.002.
• Ehrenborg, Richard (2021). "Bounding Monochromatic Triangles Using Squares". Mathematics Magazine. 94 (5): 383–386. doi:10.1080/0025570X.2021.1977581.
• Grzesik, Andrzej; Lee, Joonkyung; Lidický, Bernard; Volec, Jan (2022). "On tripartite common graphs". Combinatorics, Probability and Computing. 31 (5): 907–923. doi:10.1017/S0963548322000074.
• Zhao, Yufei (2023). Graph Theory and Additive Combinatorics: Exploring Structure and Randomness. Cambridge: Cambridge University Press. doi:10.1017/9781009310956. ISBN 978-1-009-31094-9.
• Kiem, Aldo; Pokutta, Sebastian; Spiegel, Christoph (2026). "The four-color Ramsey multiplicity of triangles". Journal of Combinatorial Theory, Series B. 179: 19–70. arXiv:2312.08049. doi:10.1016/j.jctb.2026.02.001.