16
$\begingroup$

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

Improve this question
$\endgroup$
7
  • $\begingroup$ 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$. $\endgroup$
    – bof
    Feb 12 at 10:39
  • 2
    $\begingroup$ Conjecture (iii) implies that every infinite, connected, $3$-regular, vertex-transitive graph has edge chromatic number $3$. Is this true? $\endgroup$
    – bof
    Feb 12 at 11:11
  • $\begingroup$ "Equivalently, every edge of 𝑇 lies in a double-ray." Doesn't this assume that T is infinite? $\endgroup$
    – Daniel Asimov
    Feb 13 at 1:39
  • 1
    $\begingroup$ @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? $\endgroup$
    – bof
    Feb 13 at 2:10
  • 2
    $\begingroup$ Question i) appears as question 28 in this list from 2010: users.renyi.hu/~abert/questions.pdf, attributed there to Babai. $\endgroup$
    – Gabor Lippner
    Feb 13 at 17:02

0

Reset to default

Your Answer

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