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
vertices with minimum degree at least has a Hamiltonian cycle. For
Problem 914 with and
, a graph on vertices with minimum degree at least has a
Hamiltonian cycle of even length , and alternate edges of that cycle are
disjoint copies of ; for the graph is itself. Erdős's
1967 seminar paper
(p. 56)
derives the case 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 .
Covers. The case , for every .
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 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.