Locally finite graphs with ends: A topological approach, II. Applications

NEW

Problem: Diestel’s wording is intentionally ambiguous: “$k$-highly connected” may mean $k$-edge-connected, $k$-vertex-connected, or the stronger topological $k$-connected notion allowing deletion of vertices, edges, or ends; “degree” of an end may mean vertex-, edge-, or relative degree. I analyze the admissible strong $k$-connected interpretation, with ordinary vertex-degree for vertices and vertex-degree for ends. A counterexample for this permitted reading falsifies the broad formulation.

Result: The statement is false already for $k=2$.

Let $G$ be the half-grid with vertex set $\mathbb Z\times \mathbb N_0$, horizontal edges

and vertical edges

This graph is locally finite and one-ended; call its unique end $\omega$.

Let $H\subseteq G$ contain all vertical edges and only the horizontal edges on level $0$. Thus $H$ is a tree: a double ray $\mathbb Z\times\{0\}$ with one vertical ray attached at every vertex. Let

Then $X$ contains all vertices of $G$ and the unique end $\omega$.

The subspace $X$ is $2$-connected in Diestel’s strong sense: deleting any one vertex, edge, or the end $\omega$ leaves it connected. If a vertex or edge is deleted, every component of the remaining graph still contains a ray converging to $\omega$, so the components are joined through $\omega$. If $\omega$ is deleted, the remaining graph is just the connected tree $H$.

Moreover $X$ is edge-minimal with this property. Every edge of $H$ is a bridge of the tree $H$. Hence, after deleting any edge $e$, deleting the single end $\omega$ disconnects $X-e$. Thus $X-e$ is not $2$-connected.

Now let $C$ be the closure in $X$ of the level-$0$ double ray $\mathbb Z\times\{0\}$. Since both tails converge to the same end $\omega$, $C$ is a circle. But every vertex $(i,0)\in C$ has degree $3$ in $X$, and the end $\omega$ has infinite vertex-degree in $X$, witnessed by the pairwise disjoint vertical rays. Thus $C$ contains no vertex or end of degree at most $2$.

So the proposed assertion fails for $k=2$.

Citation: Problem and terminology: Reinhard Diestel, “Locally finite graphs with ends: a topological approach,” arXiv:0912.4213. The counterexample above is given here.