On a theorem of Hans Läuchli (Q679674)

Let \(n\) be a natural number and \(P(n)\) be the following statement: If all finite subgraphs of a graph \(G\) are \(n\)-colorable, then \(G\) is \(n\)-colorable. From results of \textit{J. Mycielsky} [Acta Math. Acad. Sci. Hung. 12, 125--129 (1961; Zbl 0100.19404)] and \textit{H. Läuchli} [Isr. J. Math. 9, 422--429 (1971; Zbl 0261.04002)] it follows that \(P(m) \leftrightarrow P(n)\) for all \(m,n \geq 3\). The result heavily relies on the Boolean prime ideal theorem, and Läuchli stated the problem to give a ``direct'' proof for \(P(3) \rightarrow P(4)\). The paper under review solves this problem, i.e. it proves that \(P(3) \rightarrow P(4)\) without using the Boolean prime ideal theorem.