I’m wondering whether in the lattice graph $\mathbb{Z}^2$ one can find a subgraph which is isomorphic to the infinite complete binary tree. My guess is no, but I wouldn’t be able to prove it. Maybe in $\mathbb{Z}^3$?
I don’t know if this is trivial, in the case I’m sorry. I’m really foreign to graph theory, but this question kind of fascinates me.
On
If your definition of "subgraph" only allows edges of the original graph (i.e., if $e$ is an edge of the subgraph, then both ends of $e$ are vertices of the subgraph) rather than letting you take multiple edges and join them into one longer edge...then the answer is no.
Take the root of your binary tree, and look at all nodes that are within k = 3 edges of the root. There are 2 adjacent nodes, 4 below those, and 8 below those, so $14 = 2^k - 2$ of them.
Now consider a vertex --- say the origin -- of the lattice graph. Within h = 3 edges of that vertex are all the nodes of a diamond-shaped region...with a total of $1 + 4 + 8 + 12 = 25 = 1 + 4(1 + 2 + 3) = 1 + 4(\frac{h(h+1)}{2}) = 1 + 2h^2 + 2h$ nodes. (I got this sum by adding up the dots in 'concentric' diamonds.
But now let's look at $k = h = 7$. In the binary tree, there are $2^7 - 2 = 126$ nodes; in the lattice, there are $1 + 2*49 + 14 = 113$ nodes. Assuming you put the root of your binary tree at the origin, you cannot possibly fit the first 7 levels of your binary tree into the lattice in a way that each node is within a distance of 7 edges from the location of the root node in your lattice graph. So no... with this definition of subgraph, it's not possible.
Hint.
The number of nodes of a complete binary tree at distance $p$ from the starting node is $2^p$. The number of nodes of a cube in $Z^n$ with side $p$ is $(p+1)^n$.