Skip to main content
3 of 7
Rollback to Revision 1
bof
  • 13.4k
  • 2
  • 43
  • 66

No. For a counterexample let $H=(\omega,E)$ where $E=\{e_n:n\in\omega\}$ and $e_n=[n,\omega)=\{x\in\omega:x\ge n\}$.

If a subset $E'\subseteq E$ is finite then $(\omega,E')$ is tameable; every vertex cover contains a finite vertex cover which contains a minimal vertex cover, and every independent set is contained in a cofinite independent set which is contained in a maximal independent set.

If $E'\subseteq E$ is infinite then $(\omega,E')$ is not tameable; in fact, it has no minimal vertex cover and no maximal independent set, since the vertex covers are just the infinite subsets of $\omega$ and the independent sets are just the coinfinite subsets of omega.

Thus $\operatorname{Tame}(H)=\{E'\subseteq E:E'\text{ is finite}\}$ and $\operatorname{Max}(\operatorname{Tame}(H))=\varnothing$.

bof
  • 13.4k
  • 2
  • 43
  • 66