Notation:
- Here I'm assuming there's at most one edge between two vertices, and no edges between a vertex and itself.
- By a computable graph I mean a set $(V,E)$ where the vertex set $V$ is computable and so is the edge relation $E$.
- By the graph $\mathbb Z \times \mathbb Z$, I mean the graph that has a vertex for every element and an edge between $(a,b)$ and $(m,n)$, iff $a=m$ and $b = n \pm 1$, or $b =n$ and $a = m \pm 1$, i.e. they are either horizontally adjacent or vertically adjacent.
- By a "$G'$ is a subjraph of $G=(V,E)$", (I'm not sure if this has a name so I'm making one) I mean a graph $G'=(V', E')$ with $V' \subseteq V$, such that if $e'$ is an edge between $a$ and $b$ then there exists an edge between $a$ and $b$ in $G$ or there is a path from $a$ to $b$ that does not passes through any other vertex in $G'$. It is not required for $E'$ to have all the edges that "make sense". So this works like "removing" some vertices but keeping their edges alive by stitching them together. For example, the cyclic graph with three vertices is not a subgraph of $\mathbb Z \times \mathbb Z$ but it is a subjraph of it: take $V'=\{(0,0), (1,0), (0,1)\}$ and the missing edge between $(0,1)$ and $(1,0)$ is given by the path $(0,1) \to (1,1) \to (1,0)$, since $(1,1) \not \in V'$.
The questions:
- Is every graph with a countable amount of vertices a subjraph of $\mathbb Z \times \mathbb Z$?
- Furthermore, is every computable graph isomorphic to a computable subjraph of $\mathbb Z \times \mathbb Z$? If so, is the isomorphism computable too?
I know little about graph theory so I don't even know how to begin to do this.
The motivation:
I want to make a computer program that displays $\mathbb Z \times \mathbb Z$ and allows the user to turn off nodes and edges (by inputting two functions $f,g:\mathbb Z \times \mathbb Z \to \{0,1\}$), and I want to claim that these are all the computable graphs.
No. Any complete graph with $n\ge 3$ vertices is not a subgraph of $\mathbb Z\times\mathbb Z$. In particular, the complete graph with countably infinite vertices cannot be a subgraph of $\mathbb Z\times\mathbb Z$.Yes. See comments below.
Suppose you have a computable graph on $\mathbb Z\times\mathbb Z$, then you can construct a program such that it halts iff $(x,y)$ is an edge of this graph. On the other hand, given a program on $\mathbb Z\times\mathbb Z$, you can define a graph such that $(i,j)$ is an edge iff it halts on both $(i,j)$ and $(j,i)$. With this construction, there should be a way to exclude a large class of possibilities using the Halting problem is unsolvable.