Pairs of infinite graphs that are minors of each other

43 Views Asked by At

A graph $H$ is a minor of another graph $G$ if $H$ can be obtained from $G$ by deleting edges or vertices and contracting edges.

On finite graphs, the graph minor is a partial order $\preceq$. But this is not true on infinite graphs. Consider for example the square lattice graph $G$ (see below) and let the graph $H$ be the one where we delete all edges in every second “column” and “row”.

enter image description here

Then $G \preceq H \preceq G$ but $G \neq H$ and so the partial order is not antisymmetric.

Is anything known about such counterexamples, do they have a name? Do they have characterisation when $G$ is a lattice graph?