1
$\begingroup$

Let $G$ be a graph (of any cardinality). Suppose all its vertices have finite degree. Then does there exist an infinite non-self-intersecting path of an infinite sequence of vertices in $G$?

If not, then is it true if the supremum of the degrees in $G$ is finite?

I am comfortable assuming that $G$ is a tree.

$\endgroup$
2
$\begingroup$

Yes, provided $G$ is connected. This is precisely the content of König's lemma.

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