De Bruijn–Erdős theorem (graph theory) has been listed as one of the
Mathematics good articles under the
good article criteria. If you can improve it further,
please do so. If it no longer meets these criteria, you can
reassess it. Review: January 15, 2019. ( Reviewed version). |
A fact from De Bruijn–Erdős theorem (graph theory) appeared on Wikipedia's
Main Page in the
Did you know column on 24 July 2011 (
check views). The text of the entry was as follows:
|
This article is rated GA-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||
|
There's another "De Bruijn–Erdős theorem" that comes up occasionally in incidence geometry. It essentially states that a configuration of n points in the projective plane, not all on a line, span at least n distinct lines. The result is from the following paper:
I plan to add to this article a mention of this soon (but I'm too tired tonight). Jwesley 78 07:38, 3 April 2010 (UTC)
For sake of symmetry with its companion article " de Bruijn–Erdős theorem (incidence geometry)", I propose this article be renamed to "de Bruijn–Erdős theorem (graph theory)". Anyone object? or have an better name? Jwesley 78 23:42, 4 April 2010 (UTC)
The proof via Zorn's lemma was actually given by Lajos Pósa, as Soifer remarks in his book. It is unpublished, but Lovász wrote it up in his book Combinatorial Problems and Exercises. I think that the first to come up with that proof was Gabriel Dirac, he did not publish it either, but wrote it up in his Ph. D. thesis. Kope ( talk) 05:43, 6 April 2010 (UTC)
Does the treatment given in this dissertation by one of Sabidussi's graduate students add sufficiently to Luxemburg's to merit inclusion?? 128.172.67.235 ( talk) 18:39, 12 August 2016 (UTC)
Next sentence is unclear....
This follows immediately (what follows?)
Jumpow ( talk) 22:09, 16 May 2017 (UTC)
I was thinking about reviewing the good article nomination, but decided against it, because I don't really have any experience with math articles on Wikipedia. But I thought I might put in my two cents anyhow.
"It is a special case of the compactness theorem of Kurt Gödel stating that a set of first-order sentences has a model if and only if every finite subset of it has a model." I'm not sure this is true. Or at least I don't see how the theorem can be proved using the compactness of first-order logic. It can, however, be easily proved using the compactness of propositional logic.
Reading the article, I felt like there were a few things that could be made more accessible by providing a little more detail. For example, I think the counterexample to the theorem in models of set theory without choice could be made more easily understandable. I don't understand math without the axiom of choice, so that part I won't comment on. But maybe the argument why the graph G can be two-colored with the axiom of choice can be made clearer. Why do two vertices in G that differ by an even integer multiple of the square root of two plus a rational number require the same color? Why is the graph formed by contracting each equivalence class to a single vertex an infinite matching?
Other than that, I thought it was really interesting and well-written article. Thanks,-- Carabinieri ( talk) 16:36, 23 May 2018 (UTC)