2
$\begingroup$

I read a proof that every infinite, connected, locally finite graph contains a ray, and the proof relies on the graph being locally finite. I didn't want to assume that the lack of that condition made the assertion false, though.

$\endgroup$

2 Answers 2

5
$\begingroup$

An infinite star (a graph on vertex set $\mathbb N$ in which vertex $0$ is adjacent to vertices $1,2,3,\dots$ and there are no other edges) doesn't contain a ray or even a path of length $3$, so the graph does need to be locally finite.

$\endgroup$
2
$\begingroup$

My apologies OP I misread your question, and gave a proof that says that locally finite guarantees an infinite ray. What Misha already said. In fact, Even if you had an infinite number of infinite-degree vertices, you could still construct a graph that has has no rays:

Let $k$ be an arbitrary positive integer, and let $G$ be the graph on $V = \{a \}\cup \mathbb{Z}^1 \cup \mathbb{Z}^2 \cup \ldots \mathbb{Z}^k$, where for each positive integer $j <k$ and each $(j+1)$-tuple $(z_1,\ldots, z_j,z_{j+1}) \in \mathbb{Z}^{j+1}$ there is an edge in $G$ between $(z_1,z_2,\ldots, z_j) \in \mathbb{Z}^j$ and $(z_1,z_2\ldots, z_j,z_{j+1}) \in \mathbb{Z}^{j+1}$ (and for each integer $j$, between $a$ and $(z_1) \in \mathbb{Z}^1$).

The length of the longest path is $2k$, as one can check that the above graph specifies a tree of depth precisely $k$ (with $a$ as the root) where every internal vertex has infinite degree.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .