Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Claim. G. A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. (3) 2 (1952), 69--81, DOI 10.1112/plms/s3-2.1.69 (dated by its year only, which names this page). The paper is not held. Its Theorem 3, the number under which Dirac's 1960 paper in Math. Nachr. cites it (card), is the Hamiltonicity theorem as it is generally stated: a graph on n≥3n\ge3 vertices with minimum degree at least n/2n/2 has a Hamiltonian cycle. For Problem 914 with r=2r=2 and m≥2m\ge2, a graph on 2m2m vertices with minimum degree at least mm has a Hamiltonian cycle of even length 2m2m, and alternate edges of that cycle are mm disjoint copies of K2K_2; for m=1m=1 the graph is K2K_2 itself. Erdős's 1967 seminar paper (p. 56) derives the case r=2r=2 from Dirac's result on Hamiltonian cycles, and the site's commentary does the same. The claim value is proved: the result proves the statement for r=2r=2.

Covers. The case r=2r=2, for every m≥1m\ge1.

Depends on. Nothing in this wiki; the passage from the Hamiltonian cycle to the perfect matching is elementary and written above.

Acceptance. Refereed: published in the Proceedings of the London Mathematical Society, cited with its venue above. Reviewed: the site's curator, T. F. Bloom, independent of the author, labels the problem PROVED (LEAN) and derives the case r=2r=2 from Dirac's theorem in the commentary. The text is not held, so its statement and theorem number rest on the citations named above, and no proof step is checked.