Consider the infinite graph $G = (V,E)$, where $V = \mathbb{Z}^2$ and each element is adjacent to its 4 cardinal neighbours, i.e. $$ E = \{(u,v) \in V^2 : \text{dist}(u,v) = 1\} $$ What are the finite subgraphs of $G$? There are several properties a graph $H$ must satisfy to be (isomorphic to) a subgraph of $G$:
- $H$ must be planar
- Every vertex in $H$ must have degree at most 4
- $H$ must be bipartite
The above conditions aren't sufficient. I initially hoped the key was in the cycles of $H$, but there is even an example of a tree satisfying the above conditions which is not a subgraph of $G$, for instance, this tree: https://i.stack.imgur.com/SDVST.jpg
So my question is: is there a nice characterization of the finite subgraphs of $G$? Or at least an efficient algorithm for determining whether a particular finite graph is a subgraph of $G$?