1
$\begingroup$

I just came across the notion of ends of a space, and I wonder if the following are equivalent for $G$ a locally finite connected graph:

  1. There exists an infinite path $v_1,v_2,\dots$ in $G$ which hits every vertex at least once but not infinitely many times
  2. $G$ is 1-ended
Improve this question
$\endgroup$
4
  • $\begingroup$ No. Let $G$ be a graph with a vertex for every natural number and an edge between $n$ and $n+1$ for all $n$, and let $G_+$ denote $G$ together with an additional, isolated vertex. Then, $G_+$ is 1-ended, but there's no path that reaches all vertices of $G_+$. $\endgroup$
    – Arun Debray
    Commented Jan 13, 2018 at 19:51
  • $\begingroup$ Thanks for pointing this out, I edited to add the assumption of connectedness. $\endgroup$
    – I. Haage
    Commented Jan 13, 2018 at 19:57
  • $\begingroup$ Maybe you could mention that clearly 1 implies 2, so you want to know about the converse. $\endgroup$
    – YCor
    Commented Jan 13, 2018 at 20:26
  • 1
    $\begingroup$ The implication 2 $\Rightarrow$ 1 also is simple: just observe that for any finite connected subgraph $\Gamma$ of a 1-ended graph $G$ the complement $G\setminus\Gamma$ has finitely many connected components and exactly one of them is infinite. Using this fact, by induction, one can easily construct the required infinite path in $G$. $\endgroup$
    – Taras Banakh
    Commented Jan 13, 2018 at 21:52

1 Answer 1

Reset to default
4
$\begingroup$

I'll prove the direction that 2 implies 1.

Using that $G$ is connected and 1-ended, you can obtain an increasing sequence of connected, finite diameter subgraphs $$G'_0 \subset G'_1 \subset G'_2 \subset \cdots $$ whose union is $G$, such that for all $i$, all but one component of the subgraph $G \setminus G'_i$ has finite diameter.

Since $G$ is locally finite, it follows that each $G'_i$ is finite, each finite diameter component of $G \setminus G'_i$ is finite, and there are only finitely many such components. Letting $G_i$ be the union of $G'_i$ with the finite diameter components of $G \setminus G'_i$, we obtain an increasing sequence of connected, finite subgraphs $$G_0 \subset G_1 \subset G_2 \subset \cdots $$ whose union is $G$, such that $G \setminus G_i$ consists of a single unbounded component.

Let $P_i = G_i \cap (G \setminus G_i)$, which is a finite set of points. For convenience, I'll pass to a subsequence so that $P_i$ is contained in the topological interior of $G_{i+1}$, hence $P_i$ is disjoint from $G \setminus G_{i+1}$.

Now I'll construct the desired infinite path $\gamma$, inductively constructing a strictly increasing family of initial segments $$\gamma_0 \subset \gamma_1 \subset \gamma_2 \subset \cdots $$ The path $\gamma_0$ starts anywhere, then runs around, concatenating edges, and hitting every vertex of $G_0$, ending at some $p_0 \in P_0$. Assuming by induction that $\gamma_i$ has been constructed to hit every point of $G_i$, ending at some $p_i \in P_i$, starting from $p_i$ the path $\gamma_{i+1} \setminus \gamma_i$ runs around in $G \setminus G_i$, concatenating edges, and hitting every point of $G_{i+1} \setminus G_i$, ending at some point $p_{i+1} \in P_{i+1}$.

The path $\gamma$ does hit every vertex, by construction. Also, clearly $\gamma_{i+1}$ hits each vertex of $G_i$ only finitely many times and $\gamma_{i+2} \setminus \gamma_{i+1}$ does not hit any vertex of $G_i$, hence $\gamma$ hits each vertex only finitely many times.

Improve this answer
$\endgroup$
1
  • $\begingroup$ There seems to be some typo in your definition of $ P_i $. The last $ i$ should be $ i-1 $ probably. $\endgroup$
    – Arnaud Mortier
    Commented Jan 13, 2018 at 22:09

You must log in to answer this question.

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