# Does every infinite, connected, locally finite, vertex-transitive graph have a leafless spanning tree?

My question is

Let $$G$$ be an infinite, connected, locally finite, vertex-transitive graph. Must $$G$$ have the following substructures?
i) a leafless spanning tree;
ii) a spanning forest consisting of rays;
iii) a spanning forest consisting of double-rays.

A ray is a 1-way infinite (self-avoiding) path. A double-ray is a 2-way infinite path. A tree $$T$$ is leafless, if it has no vertex of degree 1 (a leaf). Equivalently, every edge of $$T$$ lies in a double-ray.

The following implications hold for every (infinite, connected, locally finite) graph G, vertex-transitive or not:

iii) trivially implies ii), by removing one edge from each double-ray.

iii) also implies i): given a spanning forest $$F$$ of double-rays, let $$T$$ be a minimal tree containing $$F$$, which can be constructed greedily by connecting the components of $$F$$ one by one, thereby never creating a leaf.

i) implies ii): pick a root $$r$$ of the leafless tree $$T$$, and a ray $$R$$ containing $$r$$. Delete all edges of $$T$$ incident with $$R$$ but not contained in it. Repeat in each resulting component, picking the vertex adjacent with $$R$$ as the root.

The other implications can fail for general $$G$$, but I don't know if they hold when $$G$$ is vertex-transitive.

Note that if $$G$$ is a Cayley-graph, and one of its generators has infinite order, then iii) holds. In 2009 I asked if every 1-ended, finitely generated, (connected) Cayley graph has a spanning double ray (Problem 3 in Infinite Hamilton cycles in squares of locally finite graphs), which is much stronger than iii) above, and still open as far as I know. It follows from the main result of the same paper that for every vertex-transitive $$G$$, the square $$G^2$$ satisfies iii). Here, $$G^2$$ is defined by adding an edge between each two vertices that are at distance 2 in $$G$$. In particular, every f.g. group has a f.g. Cayley graph satisfying iii) (and hence i) and ii)).

• Conjecture (iii) says in other words: every infinite, connected, locally finite, vertex-transitive graph has an acyclic $2$-regular spanning subgraph. By the usual compactness argument, this is equivalent to the ostensibly weaker assertion: if $G$ is an infinite, connected, locally finite, vertex-transitive graph, then for each finite set $X\subset V(G)$ there is a subgraph $H_X$ of $G$ such that $X\subset V(H_X)$ and every vertex in $X$ has degree $2$ in $H_X$.
– bof
Feb 12 at 10:39
• Conjecture (iii) implies that every infinite, connected, $3$-regular, vertex-transitive graph has edge chromatic number $3$. Is this true?
– bof
Feb 12 at 11:11
• "Equivalently, every edge of đť‘‡ lies in a double-ray." Doesn't this assume that T is infinite? Feb 13 at 1:39
• @DanielAsimov For an acyclic graph (in particular a tree), "every edge lies in a double ray" is equivalent to "no vertex has degree $1$". Why do you think it's necessary to assume that the graph is infinite? What finite counterexample do you have in mind?
– bof
Feb 13 at 2:10
• Question i) appears as question 28 in this list from 2010: users.renyi.hu/~abert/questions.pdf, attributed there to Babai. Feb 13 at 17:02