Why does $G \times G$ have 1 end?

59 Views Asked by At

Let $G$ be a locally finite, connected graph. Then $G \times G$ has 1 end.

This is true, if, for example, we consider $G$ to be a Cayley graph of $\mathbb{Z}$, just by looking at $\mathbb{Z}^2$, which is "obviously" single ended.

I cannot think of a rigorous argument for why $G \times G$ is single ended. If you remove a compact set $K$, you can always go around the points of $K$ in some way to get between points in $G \times G - K$. But how, exactly?

1

There are 1 best solutions below

0
On BEST ANSWER

I will assume $G$ is infinite; otherwise $G\times G$ is compact and has no ends.

Suppose $K\subset G\times G$ is compact. We may assume that in fact $K=H\times H$ for some finite full subgraph $H$ of $G$ (just take the full subgraph on the vertices of all the edges which intersect $K$; here we use the assumption that $G$ is locally finite to guarantee that the full subgraph on finitely many vertices is finite). Now suppose $x,y\in G\times G-K$. Each of $x$ and $y$ must have at least one coordinate which is not in $H$; let us suppose $x=(a,b)$ and $y=(c,d)$ where $a,c\not\in H$ (the other cases are similar). Pick a point $e\in G-H$. In $G\times G-K$, we can then find a path from $(a,b)$ to $(a,e)$ (take a path from $b$ to $e$ on the second coordinate), a path from $(a,e)$ to $(c,e)$ (take a path from $a$ to $c$ on the first coordinate), and a path from $(c,e)$ to $(c,d)$ (take a path from $e$ to $d$ on the second coordinate). Concatenating these, we get a path from $x=(a,b)$ to $y=(c,d)$, so $G\times G-K$ is connected.

(Note that for general compact $K$ not of the form $H\times H$, $G\times G-K$ may not be connected--only the complement of its bounded components is connected.)