---

Statement

The paper's Lemma, unnumbered and printed as "Lemma", p. 142.

Let $G$ be a graph on $n$ vertices and $\sigma(G)$ the largest integer $l$ such that $G$ contains a subdivision of $K_l$ (p. 141). If $G$ contains no complete subgraph $K_q$ on $q$ vertices, then

$$\sigma(G)<\sqrt{2(q-1)n}.$$

The print states no range for $q$; its proof applies Turán's theorem with the factor $\frac{q-2}{2(q-1)}$, which needs $q\ge2$.

Source. P. Erdős and S. Fajtlowicz, On the conjecture of Hajós, Combinatorica 1 (1981), no. 2, 141--143, doi:10.1007/BF02579269; the Lemma on p. 142. The edition read is identified in the source digest.

Read depth. Claims checked: the statement was read clause by clause on the page image. The proof (p. 142, about ten lines) was read for structure only and not checked.

Proof pointer

P. 142. Take the $\sigma$ branch vertices of a subdivision of $K_\sigma$. By Turán's theorem they span at most $\frac{q-2}{2(q-1)}\sigma^2$ edges, so at least $\binom\sigma2-\frac{q-2}{2(q-1)}\sigma^2$ of their pairs are non-adjacent and joined by a path of length at least two; the paths are internally disjoint, so $n$ is at least that count plus $\sigma$, which gives $\sigma^2/(2(q-1))<n$. Not reconstructed here.

Dependencies

Turán's theorem.

Bears on

• Problem 717: the upper bound on $\sigma(G)$ from which the paper derives Theorem 1, and whose counting the proof of Theorem 3 reuses; it is an ingredient of the paper's lower bounds for $\chi(G)/\sigma(G)$, not a statement of the problem.