de Bruijn-Erdős Theorem

Two distinct theorems are referred to as "the de Bruijn-Erdős theorem." One of them (de Bruijn and Erdős 1951) concerns the chromatic number of infinite graphs; the other (de Bruijn and Erdős 1948) states that every noncollinear set of n points in the plane determines at least n distinct lines.

Chen and Chvátal (2006) have partially generalized the (second) de Bruijn-Erdős theorem in the framework of metric spaces.

See also

Configuration, Sylvester's Line Problem

Explore with Wolfram|Alpha


Chen, X. and Chvátal, V. "Problems Related to a de Bruijn-Erdős Theorem." Submitted to Elsevier Preprint, Apr. 18, Bruijn, N. G. and Erdős, P. "On a Combinatorial Problem." Indag. Math. 10, 421-423, Bruijn, N. G. and Erdős, P. "A Colour Problem for Infinite Graphs and a Problem in the Theory of Relations." Indag. Math. 13, 369-373, 1951.

Referenced on Wolfram|Alpha

de Bruijn-Erdős Theorem

Cite this as:

Weisstein, Eric W. "de Bruijn-Erdős Theorem." From MathWorld--A Wolfram Web Resource.

Subject classifications