1
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ 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$... $\endgroup$
    – Dan D-man
    Feb 12, 2023 at 7:50
  • 2
    $\begingroup$ No, it's a grid, every vertex has exactly 4 neighbors. He just made a shortcut in his notation. $\endgroup$
    – Highheath
    Feb 12, 2023 at 11:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.