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

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

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.