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

| cite | improve this answer | |
$\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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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