TOPICS
Search

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

References

Chen, X. and Chvátal, V. "Problems Related to a de Bruijn-Erdős Theorem." Submitted to Elsevier Preprint, Apr. 18, 2006.de Bruijn, N. G. and Erdős, P. "On a Combinatorial Problem." Indag. Math. 10, 421-423, 1948.de 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. https://mathworld.wolfram.com/deBruijn-ErdosTheorem.html

Subject classifications