# Characterizing 1-ended graphs

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
• 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_+$. – Arun Debray Jan 13 '18 at 19:51
• Thanks for pointing this out, I edited to add the assumption of connectedness. – I. Haage Jan 13 '18 at 19:57
• Maybe you could mention that clearly 1 implies 2, so you want to know about the converse. – YCor Jan 13 '18 at 20:26
• 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$. – Taras Banakh Jan 13 '18 at 21:52

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.

• There seems to be some typo in your definition of $P_i$. The last $i$ should be $i-1$ probably. – Arnaud Mortier Jan 13 '18 at 22:09