---

Statement

$K(G)$ is the chromatic number of $G$, and $C_n$ is a circuit of $n$ edges (the paper's notation).

Theorem (Erdős, Hajnal and Shelah, the paper's reference [6]; p. 184, reported without proof). Every $G$ with $K(G)\ge\aleph_1$ contains, for some $n_0$, every $C_n$ with $n>n_0$.

Question (p. 184, quoted). "Our simplest unsolved problem states: Is it true that to every $G$ with $K(G)\ge\aleph_1$ there is an $n_0$ and an edge $e$ so that for every $n>n_0$ $G$ contains a $C_n$ passing through $e$ ?"

Source. P. Erdős, Problems and results on finite and infinite graphs, Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974), Academia, Prague, 1975, pp. 183--192; Section II, p. 184. The edition read is identified on the source card. Reference [6] is P. Erdős, A. Hajnal and S. Shelah, On some general properties of chromatic numbers, Topics in topology (Keszthely, June 1972), Colloq. Math. Soc. János Bolyai 8, North-Holland, 243--255, as the paper's list gives it.

Read depth. Claims checked: the passage was read clause by clause on the printed page. The paper gives no proof of the theorem.

Proof pointer

None in this paper; the theorem is reported with reference [6].

Dependencies

None within the paper.

Bears on

• Problem 737: the question above is the problem's question, posed here for every graph of chromatic number at least $\aleph_1$, where the problem's statement takes chromatic number $\aleph_1$.
• Problem 594: the theorem as reported here, every $C_n$ with $n>n_0$, includes every sufficiently long odd cycle, which is what the problem asks for.