I apologies if this is too trivial a question or if I am over complicating anything here. But I was hoping for some clarification in an article I was reading about forbidden graph substructures on Wikipedia.

To explain, for any class of graphs $C$ let $\neg C$ be the class of all graphs not in $C$. Now given any pre-order $\leq$ on the class of all graphs we say that a class $F$ obstructs $C$ under $\leq$ iff for every graph $G$ we have the equivalence $G\not\in C\iff \text{There exists }H\leq G\text{ isomorphic to a graph in }F$.

For example if we write that $H\leq G$ when a graph $H$ is a minor of a graph $G$ then $\leq$ is a pre-order and by Wagner's theorem if $C$ is the class of planar graphs then $\{K_5,K_{3,3}\}$ obstructs $C$ under $\leq$.

With all that said, isn't it true that there exists an inclusion minimal obstruction class for any class of graphs $C$ under any pre-order $\leq$ if and only if $(1)$ membership in $C$ is closed under isomorphisms, $(2)$ $C$ is an ideal of $\leq$ and $(3)$ every chain in the pre-order $P=(\neg C,\leq)$ has some lower bound.

Since if $(1)$ and $(2)$ are true then defining $\preceq$ to be $(\leq/\cong)$ we see $[A]_{\cong }\preceq [B]_{\cong}\iff A\preceq B$ and for any class $F$ that $(F/\cong)=\{[G]_{\cong}:G\in F\}$ is cofinal in $P'=(\neg C/\cong,\succeq)$ if and only if $F$ obstructs $C$ under $\leq$. Thus when every chain in $P$ has a lower bound this means there exists an inclusion minimal class $F$ cofinal in $P'$ so that every complete set of representatives $T$ for the graph isomorphism classes in $F$ must be an inclusion minimal obstruction class of $C$ under $\leq$. In fact if at least one non-proper class (a set) obstructs $C$ under $\leq$ then the minimum cardinality of those sets obstructing $C$ (note the existence of a non-proper class obstructing $C$ may be guaranteed or even independent of the axioms we are using for example if $\leq$ is the induced subgraph pre-order then the existence of such a set is equivalent to Vopenka's principle which is currently not known to be inconsistent with ZFC) under $\leq$ is exactly $\text{cf}(P')$ (the cofinality of the pre-order $P'$). While note in particular for all $G\in T$ that $G\not\in C$ and $\forall H<G(H\in C)$ or as described on Wikipedia:

Now this seems trivial however https://en.wikipedia.org/wiki/Forbidden_graph_characterization (current revision) just assumes condition $(3)$ is always true. Which I don't think is correct, unless we're only working with finite graphs. Am I in the wrong here? Or is the author of the article?

2more comments