Problem 916

Does every graph with $n$ vertices and $2n-2$ edges contain a cycle and another vertex adjacent to three vertices on the cycle?

Second statement

When $n\ge4$ , does every graph with $n$ vertices and $2n-2$ edges contain a cycle and another vertex adjacent to three vertices on the cycle?

Source: erdosproblems.com/916

Graph theory
Cycles

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

PROVED, the site's label, which describes the corrected Statement: the commentary credits the proof to Thomassen [Th74]. The result is recorded as an accepted full claim: Thomassen's Theorem ([Th74], Arch. Math. (Basel) 25 (1974), 210--215, refereed; p. 212) gives every graph with $n\ge3$ vertices and at least $2n-2$ edges a cycle and a vertex off it joined to at least three of its vertices, which covers the corrected Statement's $n\ge4$ , and Carmesin's refereed paper of 2023 restates it. The value $2n-2$ is exact: Dirac's Satz 6 (p. 68) is best possible by the graphs of his Figures 3--5, which have $2n-3$ edges and no subdivision of $K_4$ at all, and by Thomassen's Lemma 2 (p. 211) every $(K_3,K_{3,3})$ -cockade has $2n-3$ edges and lacks the configuration. The proof (pp. 212--215) is read for its structure only; no step is checked.

Notes

The site's wording carries no range for $n$ and fails at $n=1$ : the one-vertex graph has $2\cdot1-2=0$ edges and contains no cycle, so the answer there is no. At $n=2$ and $n=3$ no simple graph has $2n-2$ edges ( $2>\binom22$ and $4>\binom32$ ), so the question is vacuous; from $n=4$ on, $2n-2\le\binom n2$ and the question is the one the sources answer. These instances are checked by hand and need no source; the observation is this corpus's own and is the only result about the site's wording, credited here and counted for nothing. The change inserts "When $n\ge4$ ," before the question. The evidence is the poser's own words: Erdős poses the question in [Er67b] (printed p. 57) as a strengthening of "Dirac's result mentioned above", which he states on printed p. 56 as "when $n\ge4$ , every graph $G(n;2n-2)$ contains a subgraph homeomorphic to $K_4$ "; Dirac's Satz 6 ([Di60], p. 68) carries the same hypothesis $N\ge4$ . The defect is already in the poser's text and is not the site's: the question sentence of [Er67b] and the definition of $h_3(n)$ in [BoEr62] (pp. 144--145) give no range, and the site's wording follows them. The failures lie only at the smallest values of $n$ , so they are boundary failures.

Er67b: Erdős, P., Extremal problems in graph theory. A Seminar on Graph Theory, Holt, Rinehart and Winston, New York (1967), 54--59; the site's reference text reads "A Seminar on Graph Theory (1967), 54-59. (MR 223263)". The question, printed p. 57 = copy p. 4, and Dirac's theorem with $n\ge4$ , printed p. 56 = copy p. 3, of the re-typeset archive copy. Library home: Erdős 1967; paged at Erdős 1967, Question (p. 57 = copy p. 4).
BoEr62: Bollobás, B. and Erdős, P., Gráfelméleti szélsőértékekre vonatkozó problémákról (On extremal problems in graph theory). Mat. Lapok 13 (1962), 143--152 (in Hungarian); pp. 144--145, the question with the definition of $h_3(n)$ . Not a site key for this problem. Library home: Bollobás 1962; paged at Bollobás 1962, Question (pp. 144–145).
Th74: Thomassen, Carsten, A minimal condition implying a special $K_4$ -subdivision in a graph. Arch. Math. (Basel) 25 (1974), no. 1, 210--215, doi:10.1007/BF01238666 (Crossref record accessed; issued December 1974). The Introduction with Erdős's suggestion, p. 210; the definition of property $p$ and Lemma 2, p. 211; the Theorem, p. 212; the Corollary, p. 215. Library home: Thomassen 1974; paged at Thomassen 1974, Theorem (p. 212).
Ca23: Carmesin, Johannes, Characterising graphs with no subdivision of a wheel of bounded diameter. J. Combin. Theory Ser. B 161 (2023), 21--51, doi:10.1016/j.jctb.2023.01.004 (open access, CC BY; Crossref record accessed). Not a site key. The attestation, p. 22; its reference [16] is [Th74]. Library home: Carmesin 2023; paged at Carmesin 2023, Related results (p. 22).
Di60: Dirac, Gabriel Andrew, In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen. Math. Nachr. 22 (1960), no. 1--2, 61--85, doi:10.1002/mana.19600220107. Satz 6, printed p. 68 (the paper has 25 pages, printed pp. 61--85; "Eingegangen am 12. 10. 1959", p. 61), with its proof and the sentence that the graphs of Figures 3--5 (p. 67) show it best possible: the $2n-2$ theorem on subdivisions of $K_4$ with the hypotheses finite and $N\ge4$ , stated by Erdős in [Er67b] for $n\ge4$ and in [BoEr62], and reproved for $n\ge3$ as the Corollary (p. 215) of [Th74], which cites it as [1, Satz 6]. Library home: Dirac 1960; paged at Dirac 1960, Satz 6.

Problem 916

Second statement

Status

Notes

Proof claims

Discussion