# Infinite Graph with Finite Degree

Let $$G$$ be an undirected graph with an infinite number of vertices (and edges), and assume it is connected in the sense every $$u,v$$ have at least one path connecting them. Assume each vertex has a finite degree. My question is: Is it possible for a pair of vertices to exist, such that they will have an infinite number of paths?

Ofcourse, if we allow a path to contain a cycle, the answer is positive. However, I am interested in what happens when we forbid paths that contain cycles.

In other words: Is it possible for a pair of vertices to exist, such that they will have an infinite amount of simple paths?

The lattice $$\mathbb{Z}^2$$ gives an example. Take $$u=(0,0)$$ and $$v=(0,1)$$. For every $$n$$ we can construct the path $$u = (0,0) \to (n, 0) \to (n, 1) \to (0, 1)=v$$ of length $$2n+1$$. Each of these paths is distinct and contains no cycle.
The same works for any selection of vertices $$u$$ and $$v$$.
• Each vertex should have a finite degree. In your example, what is the degree of $(0,0)$? It seems to have an edge $(n,0)$ for any $n$... Commented Feb 12, 2023 at 7:50