Graphs of diameter two with no 4-circuits (Q1301629): Difference between revisions

Theorem: Let \(G\) be a simple graph with diameter two and no 4-circuit. Then one of the following is true: (a) The maximum degree is \(n-1\); (b) \(G\) is a Moore graph (i.e. a regular simple graph with diameter 2 and girth 5); (c) \(G\) is a polarity graph (i.e.\ a graph \(G=(V,E)\) associated with a polarity of a projective plane---\(V\) is the point-set of the plane; \(pq\in E\) iff \(p\neq q\) and \(p\) lies on the polar line of \(q\)). Author Bondy acknowledges that their result, which dates back to 1979, was ``subsumed by a theorem of W. M. Kantor'' [Moore geometries and rank \(3\) groups having \(\mu=1\). Q. J. Math. Oxf., II. Ser. 28, No. 111, 309-328 (1977; Zbl 0406.05020)], but states that ``In the intervening years it has become apparent that this particular case of Kantor's theorem, with its attractive statement and simple proof, is not as widely known as perhaps it merits. For this reason Erdős proposed to me that we resubmit the article for publication''.