A Kuratowski theorem for nonorientable surfaces (Q1821111)

Let \(\Sigma\) denote a surface. A graph G is irreducible for \(\Sigma\) provided that G does not embed in \(\Sigma\), but any proper subgraph does so embed. Let I(\(\Sigma)\) denote the set of graphs without degree two vertices which are irreducible for \(\Sigma\). Observe that a graph embeds in \(\Sigma\) if and only if it does not contain a subgraph homeomorphic to a member of I(\(\Sigma)\). For example, Kuratowski's theorem shows that \(I(\Sigma)=\{K_{3,3},K_ 5\}\) when \(\Sigma\) is the sphere. In this paper we prove that the set I(\(\Sigma)\) is finite for each nonorientable surface, settling in part a conjecture of Erdős from the 1930's.