\documentclass[12pt]{article} \usepackage{e-jc} \usepackage{amsthm,amsmath,amssymb,amsfonts} \usepackage{graphicx} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} \let\su=\sup \def\sup{\su\>} \def\C{{\cal C}} \def\supe{\supseteq} \let\supset=\supseteq \def\sm{\smallsetminus} \usepackage{enumerate} % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} % Definitions of own macros and commands \newcommand{\COMMENT}[1]{} \def\th{\thinspace} % non-breakable thin space \def\N{\mathbb N} \def\Z{\mathbb Z} \def\Q{\mathbb Q} \def\R{\mathbb R} \def\sube{\subseteq} \let\sub=\sube \def\noskip{\vskip-\lastskip\noindent}%use after display followed by short line \newcommand{\inff}{\inf} \newcommand{\mi}{\min} \def\es{\emptyset} \newcommand{\foral}{\forall} % % % % % % % % % % % % % % % % % % % % % % \title{\bf Forcing finite minors in sparse infinite graphs by large-degree assumptions} \author{Reinhard Diestel\\ \small Mathematisches Seminar\\[-0.8ex] \small Universit\"at Hamburg\\[-0.8ex] \small Hamburg, Germany\\} \date{\dateline{02.11.2012}{30.08.2014}\\ \small Mathematics Subject Classifications: 05C07, 05C35, 05C63, 05C83} \begin{document} \maketitle \begin{abstract} Developing further Stein's recent notion of relative end degrees in infinite graphs, we investigate which degree assumptions can force a locally finite graph to contain a given finite minor, or a finite subgraph of given minimum or average degree. This is part of a wider project which seeks to develop an extremal theory of sparse infinite graphs. % keywords are optional \bigskip\noindent \textbf{Keywords:} infinite graph, degree, end, extremal \end{abstract} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section*{Introduction} Perhaps the most basic question in extremal graph theory asks which average degree assumptions force a finite graph~$G$ to contain a given desired substructure. When this substructure is not a subgraph, but a given minor or topological minor~$H$, its presence can be forced by making the average degree of $G$ large enough in terms of~$H$ only, independently of the order of~$G$. When $G$ is infinite, this will no longer work: since infinite trees can have arbitrarily large degrees, no minimum degree assumption can force an infinite graph to contain even a cycle. However, just as a finite tree with internal vertices of large degree has many leaves, an infinite tree of large minimum degree has many ends. The question we pursue in this paper is which notion of `degree' for ends might imply that an infinite graph whose vertices {\sl and} ends have large degree contains a given finite minor. (The ends of a tree should then have degree~1, so that trees are no longer counterexamples.) Various notions of end degrees already exist, but only one of them, due to Stein\th \cite{refMayaBanff}, can achieve this aim. While this was a crucial step forward, the exact notion of the `relative' end degrees she proposed still leaves room for improvement: it can be hard to verify that a given graph has large end degrees in this sense, indeed there seem to be only few sparse graphs that do. Our aim in this paper is to develop the notion of relative end degree further, so that more graphs satisfy the premise that both their vertices and their ends have degree at least some given $k\in\N$, while keeping the notion strong enough that large vertex and end degrees can force any desired finite minor. To indicate the notion of end degree that we have in mind, let us look at a locally finite connected graph $G$ of minimum degree~$k$ which, however, has no finite subgraph of minimum degree at least~$k$. (Such a subgraph would be good enough for us: recall that for every finite graph $H$ there exists an integer~$k$ such that every finite graph of minimum degree at least~$k$ contains $H$ as a minor.) If $G$ has a finite set $S$ of vertices such that every component $C$ of $G-S$ is such that all its vertices with a neighbour in~$S$ have degree at least~$k$ in the subgraph $G[S,C]$ of $G$ they induce together with~$S$, then $S$ and its neighbours in~$G$ induce a subgraph of minimum degree at least~$k$ in~$G$, as desired. If not, then a standard compactness argument will give us a sequence $C_0\varsupsetneq C_1\varsupsetneq\dots$ of `bad' components $C_n$ of $G-S_n$ for finite vertex sets~$S_n$ which identifies a unique end of~$G$. The fact that all these $C_n$ are `bad', i.e., contain a neighbour of~$S_n$ whose degree in $G[S_n,C_n]$ is less than~$k$, should then imply that this end has degree~$2$. In Section~4 we use topological methods to prove a positive result for graphs with uncountably many ends, which can also be used to strenghten our result from Section~2. All graphs in this paper are locally finite. Notation and terminology for infinite graphs, including their ends, can be found in\th \cite{refBook}. % % % % % % % % % % % % % % % % % % % % % % % % \section{End degrees, and statements of results} The simplest, and historically first, notion of degree for an end is the maximum number of either disjoint or edge-disjoint rays in its graph that represent it. This notion was introduced by Halin\th \cite{refHalinEnd}, who also showed that these maxima exist. Replacing in this definition the rays in an end with arcs converging to it in the Freudenthal compactification of the graph yields a more refined topological notion of end degree\th \cite{refBook,refTopSurvey}. An assumption of large end degrees in this sense, as well as of large vertex degrees, can force some substructures in locally finite infinite graphs, such as an unspecified highly connected subgraph\th \cite{refTopSurvey,refMayaEndDeg,refMayaBanff}. However, it will not yield the kind of result we are seeking here: for every integer~$k$ there are planar graphs with all vertex and end degrees at least~$k$, and hence no such degree assumption can force even a $K_5$ minor. (Indeed, if we draw the $k$-regular infinite tree in the plane and then add edges to turn each level into a cycle, we obtain a planar graph with only one end, and this end has infinite degree in all the senses discussed above.) It was in this situation that Stein\th \cite{refMayaBanff} suggested a notion of a `relative' end degree, which would measure for a given end the ratios between the edge and the vertex boundaries of smaller and smaller regions of the graph around this end. Before we get to our main results, let us define a simplified and slightly optimized% \COMMENT{} version of this formally, and state the theorem it leads to. Given a subgraph or vertex set $U$ in a locally finite graph~$G$, let us call $$V^+(U) := N(G-U)\ \ (\sub U)$$ its \emph{vertex boundary}. If $U$ is finite, we write $$d_G(U) := \sum_{v\in U} d_G(v)\> \big/\> |U|$$\noskip\medskip\noindent for its `average degree in~$G$'. A \emph{region} of $G$ is a connected induced subgraph $C$ with a finite vertex boundary. Since $G$ is locally finite, the neighbourhood $S=N(C)$ of $C$ in $G$ will then also be finite. Indeed, the regions of $G$ are precisely the subgraphs arising as components of subgraphs $G-S$ with $S\sub V(G)$ finite. We then write $G[S,C]:= G[S\cup V^+(C)]$, which is a finite graph, and call \[\delta^+_G (C) := \mi_{v\in V^+(C)} d_{G[S,C]}(v)\] the \emph{minimum} and \[d^+_G (C) := d_{G[S,C]}(V^+(C))\] % \COMMENT{} the \emph{average out-degree} of $C$ in~$G$. A sequence $C_0\varsupsetneq C_1\varsupsetneq\dots$ of regions is a \emph{defining sequence} for an end~$\omega$ of~$G$ if every $C_n$ contains a ray from~$\omega$ and $\bigcap_n C_n = \es$. (This latter condition ensures that $\omega$ is the only end with a ray in every~$C_n$.)% \COMMENT{} Following the ideas of Stein\th \cite{refMayaBanff}, let \begin{align*} \delta^-(\omega) &:= \inff_{C_0\varsupsetneq C_1\varsupsetneq\dots}\ \lim_{n\to\infty} \ \delta^+_G(C_n)\\ d^-(\omega) &:= \inff_{C_0\varsupsetneq C_1\varsupsetneq\dots}\ \lim_{n\to\infty} \ d^+_G(C_n), \end{align*} where both infima are taken over all defining sequences $C_0\varsupsetneq C_1\varsupsetneq\dots$ of~$\omega$ such that the limit under the infimum exists (with $\infty$ allowed). \COMMENT{} Thus, $\delta^-(\omega)$ is either infinite or the least integer~$k$ such that $\omega$ has a defining sequence with all minimum out-degrees equal to~$k$. It is not hard to show for either notion that there always exists a defining sequence of regions whose out-degrees converge, possibly to~$\infty$; in the case of $\delta^-(\omega)$ the infimum is attained by a constant sequence.% \COMMENT{} Indeed, if we changed the limit in either definition to a limes inferior or a limes superior, the values of $\delta^-(\omega)$ or $d^-(\omega)$ would not change.% \COMMENT{} The following is a variant of Stein's theorem\th \cite{refMayaBanff} based on our definitions: \begin{theorem} \label{xxxNaiveThm} Let $G$ be a locally finite infinite% \COMMENT{} graph, $k\in\N$, and $q\in\Q$. \begin{enumerate}[\rm(i)] \item If $\delta(G)\ge k$ and $\delta^-(\omega)\ge k$ for every end $\omega$ of~$G$, then $G$ has a finite subgraph of minimum degree~$\ge k$. \item If $d_G(S)\ge q$ for every large enough% \footnote{This is made precise after the statement of Theorem~\ref{xxxCtble}.} finite set $S\sub V(G)$, and $d^-(\omega) > q$ for every end $\omega$ of~$G$, then $G$ has a finite subgraph of average degree~$> q$.% \COMMENT{} \end{enumerate} \end{theorem} \begin{proof} As indicated in the Introduction. Note that the definitions of $\delta^-(\omega)$, $d^-(\omega)$ and $d_G(S)$ are chosen exactly so as to make this approach work. \COMMENT{} \end{proof} Natural though it may seem, Theorem~\ref{xxxNaiveThm} has a serious snag: it is not clear how many graphs it applies to. Although one can, for every~$k$, construct graphs that satisfy the premise of (i) and~(ii), there do not appear to be many such graphs.% \COMMENT{} Indeed, the premise in~(i), say, that $\delta^-(\omega)\ge k$ for every end~$\omega$, means that \emph{every} defining sequence $C_0\varsupsetneq C_1\varsupsetneq\dots$ for~$\omega$ is such that $\delta_G^+ (C_n)\ge k$ for~$n$ large enough. Since it is easy to construct pathological defining sequences of ends, this is rather a strong property, and easy to foil.% \COMMENT{} The same problem applies to Stein's original notion of relative end degrees; see\th \cite{refMayaBanff},\th \cite{refMayaZamora} for a discussion.% \COMMENT{} It is tempting, therefore, to change the definition of end degrees considered above by replacing their infimum with a supremum. Then an end $\omega$ will satisfy $\delta(\omega)\ge k$ as soon as there \emph{exists} a defining sequence $C_0\varsupsetneq C_1\varsupsetneq\dots$ for it in which for infinitely many (equivalently: for all) $n$ all boundary vertices of $C_n$ have degree~$\ge k$ in~$G[S_n,C_n]$. The premise of the theorem that all these end degrees are at least~$k$ thus becomes much weaker and easier to verify, and it is easy to construct a large diversity of examples of such graphs.% \COMMENT{} Thus, formally, we let \begin{align*} \delta^+(\omega) &:= \su_{C_0\varsupsetneq C_1\varsupsetneq\dots}\ \lim_{n\to\infty} \ \delta^+_G(C_n)\\ \displaystyle d^+(\omega) &:= \su_{C_0\varsupsetneq C_1\varsupsetneq\dots}\ \lim_{n\to\infty} \ d^+_G(C_n), \end{align*} the suprema being taken over all defining sequences $C_0\varsupsetneq C_1\varsupsetneq\dots$ of~$\omega$ such that the limit under the infimum exists (with $\infty$ allowed).% \COMMENT{} Let us call $\delta^+(\omega)$ the \emph{minimum limit degree} of~$\omega$, and $d^+(\omega)$ its \emph{average limit degree}. %Note that we no longer require formally in these definitions that the graphs $G-C_n$ be connected. This requirement would now make it harder, rather than easier, for $\delta^+(\omega)$ or $d^+(\omega)$ to be large, so theorems assuming large limit end degrees in their premise will be stronger without it. We shall prove such a theorem in Section~4. In its full generality, the analogue of Theorem~\ref{xxxNaiveThm} with this much weaker premise is now too strong to be true. To see this, let us show that every end $\omega$ of the infinite $k$-branching tree $T_k$ has a defining sequence witnessing that $\delta^+(\omega)\ge k$ (while $T_k$ clearly has no finite subgraph of minimum degree~$>1$). To obtain such a sequence, let each $C_n$ be the up-closure in~$T_k$ of a vertex~$t$ together with its lower neighbour~$t^-$. Then $V^+(C_n) = \{t^-\}$, and $S_n = N(C_n)$ consists of the upper neighbours of $t^-$ other than~$t$, and its lower neighbour. The vertex $t^-$ sends $k$ edges to $S_n$ (unless $t^-$ is the root of~$T_k$, a~case we can ignore), so $\delta^+_G (C_n) = d^+_G (C_n) = k$.% \COMMENT{} We shall therefore need some restrictions in order to get positive results. One such restriction is suggested by the counterexample just discussed, which relies on the fact that the neighbourhoods of the end-defining regions used are disconnected. If we ask that these neighbourhoods be connected, or just that the graphs $G-C_n$ be connected (a~slightly weaker assumption), we get our first positive result: \begin{theorem} \label{xxxCtble} Let $G$ be a locally finite infinite% \COMMENT{} graph with at most countably many ends, and let $k\in\N$ and $q\in\Q$. \begin{enumerate}[\rm (i)] \item If $\delta(G)\ge k$, and if every end $\omega$ of~$G$ satisfies $\delta^+(\omega)\ge k$ witnessed by a defining sequence $C_0\varsupsetneq C_1\varsupsetneq\dots$ such that $G-C_n$ is connected for all~$n$,\penalty-200\ then $G$ has a finite subgraph of minimum degree~$\ge k$. \item If $d_G(S)\ge q$ for every large enough finite set $S\sub V(G)$, and every end $\omega$ of~$G$ satisfies $d^+(\omega) > q$ witnessed by a defining sequence $C_0\varsupsetneq C_1\varsupsetneq\dots$ such that $G-C_n$ is connected for all~$n$, then $G$ has a finite subgraph of average degree~$>q$. \end{enumerate} \end{theorem} \noindent The `large enough' in (ii) can be taken with respect to size, or to mean that only sets $S$ containing some given set $S_0$ have to satisfy $d_G(S)\ge q$. The point is that allowing singleton sets $S$ would make the condition $\foral S\: d_G(S)\ge q$ stronger than $\delta(G)\ge q$, which is not the intention.% \COMMENT{} We shall prove Theorem~\ref{xxxCtble} in Section~2. In Section~4 we use topological methods to strengthen Theorem~\ref{xxxCtble} by dropping the requirement that the graphs $G-C_n$ be connected (Corollary~\ref{xxxCtbleTop}). The proof will assume familiarity with the more elementary proof of Theorem~\ref{xxxCtble} given in Section~2. \bigskip The assumption that $G$ should have only countably many ends is a non-trivial restriction: it is not rare that theorems that are difficult in general are much easier to prove under this assumption. So I tried for some time to prove the general version (with the additional requirement that the graphs $G-C_n$ be connected, which our earlier example has shown to be necessary)~-- but ended up finding a counterexample:\looseness=-1 \begin{theorem} \label{xxxUnctble} For every integer $k$ there exists a locally finite graph $G$ with $\delta(G)\ge k$ all whose ends $\omega$ have minimum limit degree~$\delta^+(\omega)\ge k$, witnessed by a defining sequence $C_0\varsupsetneq C_1\varsupsetneq\dots$ such that $G-C_n$ is connected for all~$n$,% \COMMENT{} but which has no finite subgraph~$H$ with $\delta(H)>2$. \end{theorem} \noindent Thus, Theorem~\ref{xxxCtble} is best possible in this sense. The counterexample proving Theorem~\ref{xxxUnctble} will be described in Section~3. \bigskip We shall finally prove a positive result for graphs with uncountably many ends. The naive extension of Theorem~\ref{xxxCtble}\th(i) to arbitrary locally finite graphs~$G$ (which is false by Theorem~\ref{xxxUnctble}) could be rephrased, without mentioning end degrees explicitly, as saying that $G$ has a finite subgraph of minimum degree at least~$k$ as soon as $\delta(G)\ge k$ and every end has a defining sequence $C_0\varsupsetneq C_1\varsupsetneq\dots$ of regions all of minimum out-degree at least~$k$. Our positive result says that this is true if these regions can be taken from one overall set of regions of $G$ that are \emph{nested}: such that any two of them are either disjoint or such that one contains the other. Note that, unlike in Theorem~\ref{xxxCtble}, we no longer require that the graphs $G-C_n$ be connected. It is not uncommon for a collection of regions defining ends to be nested. For example, if $T$ is a normal spanning tree of~$G$, the up-closures in~$T$ of single vertices form a nested set of regions in which every end has a defining sequence. In the topological terminology to be introduced in Section~4, our result takes the following form: \begin{theorem} \label{xxxPos} Let $G$ be locally finite infinite% \COMMENT{} graph with a nested set $\C$ of regions defining a basis of~$|G|$, and let $k\in\N$ and $q\in\Q$. \begin{enumerate}[\rm (i)] \item If $\delta(G)\ge k$ and $\delta^+_G(C)\ge k$ for every $C\in\C$, then $G$ has a finite subgraph of minimum degree~$\ge k$. \item If $d_G(S)\ge q$ for every large enough finite set $S\sub V(G)$, and ${d^+_G(C)> q}$ for every $C\in\C$, then $G$ has a finite subgraph of average degree~$>q$.% \COMMENT{} \end{enumerate} \end{theorem} \noindent Theorem~\ref{xxxPos} will be proved in Section~4. % % % % % % % % % % % % % % % % % % % % % % % % % % %\beginsection 2. Graphs with countably many ends \section{Elementary positive results} To make our proof of Theorem~\ref{xxxCtble} easy to describe we need a few more terms. An end of $G$ \emph{lives in} a region $C$ if each of its rays has a tail in~$C$; then it cannot also live in another region disjoint from~$C$. Given $k\in\N$, let us call a region~$C$ \emph{good} for the purpose of the proof of Theorem~\ref{xxxCtble}\th(i) if $G-C$ is connected and $\delta^+_G (C)\ge k$, and \emph{good} for the purpose of the proof of Theorem~\ref{xxxCtble}\th(ii) if $G-C$ is connected and $d^+_G (C) > q$. The assumptions of $\delta^+(\omega)\ge k$ in Theorem~\ref{xxxCtble}\th(i) and of $d^+(\omega) > q$ in Theorem~\ref{xxxCtble}\th(ii) thus imply that $\omega$ has a defining sequence consisting of good regions.% \COMMENT{} To prove Theorem~\ref{xxxCtble}, let us restate it more formally in its part~(ii): \begin{theorem} \label{xxxCtbleRestated} Let $G$ be a locally finite infinite% \COMMENT{} graph with at most countably many ends, and let $k\in\N$ and $q\in\Q$. \begin{enumerate}[\rm (i)] \item If $\delta(G)\ge k$, and if every end $\omega$ of~$G$ satisfies $\delta^+(\omega)\ge k$ witnessed by a defining sequence $C_0\varsupsetneq C_1\varsupsetneq\dots$ such that $G-C_n$ is connected for all~$n$,\penalty-200\ then $G$ has a finite subgraph of minimum degree~$\ge k$. \item If there exists a finite set $S_0\sub V(G)$ such that $d_G(S)\ge q$ for every finite set $S\sub V(G)$ containing~$S_0$, and every end $\omega$ of~$G$ satisfies $d^+(\omega) > q$ witnessed by a defining sequence $C_0\varsupsetneq C_1\varsupsetneq\dots$ such that $G-C_n$ is connected for all~$n$, then $G$ has a finite subgraph of average degree~$>q$. \end{enumerate} \end{theorem} \begin{proof} (i) We may clearly assume that $G$ is connected. Let $\omega_1, \omega_2,\dots$ be an enumeration of the ends of~$G$. Our first aim is to select an increasing sequence $S_0\sub S_1\sub\dots$ of non-empty% \COMMENT{} finite sets of vertices satisfying the following four conditions for~$n>0$: % \begin{equation} \text{The end }\omega_n \text{ lives in a good component }C_n \text{ of } G-S_n; \end{equation} \begin{equation} G[S_n] \text{ is connected}; \end{equation} \begin{equation} \text{every component of } G-S_n \text{ is infinite}; \end{equation} \begin{equation} \text{any good component of }G-S_{n-1} \text{ is also a good component of } G-S_n. \end{equation} As $S_0$ we take a finite set of vertices satisfying (2) and (3) for $n=0$; this can be obtained, for example, by taking a single vertex $v$ and adding all finite components of $G-v$. We now assume that we have chosen $S_0\sub\dots\sub S_n$ for some~$n$ so as to satisfy (2)--(3) if $n=0$, and (1)--(4) if $n>0$. Let us now choose~$S_{n+1}$. If the component $C$ of $G-S_n$ in which $\omega_{n+1}$ lives is good, we let $S_{n+1} := S_n$ and $C_{n+1}:= C$. If $C$ is bad, we choose a good region $C_{n+1}\sub C$ of~$G$% \COMMENT{} in which~$\omega_{n+1}$ lives; this exists by our assumption that $\delta^+(\omega_{n+1})\ge k$.% \COMMENT{} Note that every $S_n$--$\,C_{n+1}$ path in $G$ meets~$N(C_{n+1})$ before it reaches~$C_{n+1}$.% \COMMENT{} Since $G-C_{n+1}$ is connected (as $C_{n+1}$ is good), and $G[S_n]$ is connected by~(2), we can make $N(C_{n+1})$ connected by adding finitely many finite paths from $G[S_n\cup V(C)] -C_{n+1}$. We can therefore find a finite connected subset $S'_n$ of $S_n\cup V(C)$ that contains $S_n\cup N(C_{n+1})$ but does not meet~$C_{n+1}$, and let $S_{n+1}$ be obtained from $S'_n$ by adding any finite components of $C - S'_n$. Then $C_{n+1}$ is a component of~$G-S_{n+1}$. The set $S_{n+1}$~contains~$S_n$ but is still finite, and it satisfies (1)--(4) for~$n+1$. This completes the choice of $S_0\sub S_1\sub\dots\>$. Let us show that the above construction in fact breaks off after finitely many steps, i.e., that the sequence of sets~$S_n$ becomes stationary. If not, then $S := \bigcup_{n=0}^\infty S_n$ is infinite and spans a connected subgraph of~$G$, by~(2). As $G$ is locally finite, this subgraph contains a ray, from the end~$\omega_k$ of~$G$, say. By~(1), the end $\omega_k$ lives in the good component $C_k$ of~$S_k$, which by~(4) is still a component of $G-S$. Hence $S_k$ is a finite set of vertices separating $C_k$ from~$S$, both of which contain a ray from~$\omega_k$, a contradiction. We have shown that our construction of sets $S_0\sub S_1\sub\dots$ breaks off after finitely many steps, with a set $S_n$ say. By~(3), every component $C$ of $G-S_n$ is infinite; let us show that it is a good region of~$G$. Since $C$ is locally finite it contains a ray. Hence some end of $G$ lives in~$C$; let $\omega_k$ be such an end with $k$ minimum. By~(1), the end~$\omega_k$ also lives in the good component $C_k$ of~$G-S_k$. If $k\le n$, then $C_k$ is still a component of~$G-S_n$, by~(4), so $C=C_k$ is good. If $n < k$, then by the maximality of~$n$ we have $S_k = S_n$. So $C_k$ is also a component of~$G-S_n$, and hence equal to~$C$. Since every component of $G-S_n$ is good, every vertex of the finite non-empty% \COMMENT{} graph $H := G[S_n\cup N(S_n)]$ that is not in~$S_n$ has degree at least~$k$ in~$H$. But so do the vertices in~$S_n$, since they have degree~$\ge k$ in~$G$ and $H$ contains all their neighbours. Thus, having found $H$ we have completed the proof of~(i). (ii) The proof follows the same lines as above, except that we start with $S_0$ as specified in the statement of~(ii).% \COMMENT{} Then at the end it takes a short argument to see that if every component of $G-S_n$ is good then the finite graph $H = G[S_n\cup N(S_n)]$ has average degree~$>q$. Checking this, however, is immediate from the definitions of $d_G(S_n)$ (which is at least~$q$ by assumption) and of~$d^+_G (C)$ for the components $C$ of~$G-S_n$ (which are all~$>q$), and we leave it to the reader.% \COMMENT{} \end{proof} % % % % % % % % % % % % % % % % % % % % % % % % % % % %\beginsection 3. A locally finite counterexample with continuum many ends \section{A counterexample} We already saw that Theorem~\ref{xxxCtble} does not extend to graphs with uncountably many ends if, at the same time, we drop the additional requirement on our defining sequences $C_0\supsetneq C_1\supsetneq\dots$ of ends that also the complements $G-C_n$ must be connected. However, the counterexample we saw~-- the $k$-branching tree $T_k$ with some specially chosen defining sequences for its ends~-- relied heavily on the fact that the graphs $G-C_n$ were allowed to be disconnected: this enabled us to give the $C_n$ a small vertex boundary sending many edges out: to many components of $G-C_n$, and thus not forcing high degrees outside~$C_n$. (It will become clearer below why this would otherwise likely be the case.) We now construct a counterexample in which the graphs $G-C_n$ are connected: \begin{theorem} \label{xxxUnctbleRestated} For every integer $k$ there exists a locally finite graph $G$ with $\delta(G)\ge k$ all whose ends $\omega$ have minimum limit degree~$\delta^+(\omega)\ge k$, witnessed by a defining sequence $C_0\varsupsetneq C_1\varsupsetneq\dots$ such that $G-C_n$ is connected for all~$n$,% \COMMENT{} but which has no finite subgraph~$H$ with $\delta(H)>2$. \end{theorem} \begin{proof} Let $k$ be given, without loss of generality $k\ge 1$. Let $T$ be the rooted tree in which every vertex $t$ has $k+1$ successors, which we think of as lying \emph{above}~$t$. Let us call the vertices of $T$ \emph{tree-vertices}, and its edges \emph{vertical}. For each $t\in T$ furnish its set of $k+1$ successors with \emph{horizontal} edges to turn it into a complete graph~$K_{k+1}$, then subdivide each of these horizontal edges once. We continue to call the subdivided edges \emph{horizontal}, and call the new vertices the \emph{subdividing vertices}. Call this graph~$T^+$. Now iterate the following construction step $\omega$ times: with every subdividing vertex $s$ of the current graph identify the root of a new copy of~$T^+$, putting it above~$s$. (Keep all labels `horizontal' or `vertical' of the old graph and of the copies of $T^+$ added to it.) We will show that the resulting graph~$G$ proves the theorem. Clearly, $\delta(G)\ge k$. To show that every end $\omega$ has a minimum limit degree as stated, let us define a set $\C$ of regions $C$ with $\delta^+_G(C) = k$ and $G-C$ connected, and such that every end has a defining sequence of regions in~$\C$. The set $\C$ will consist of one region $C_s$ for every subdividing vertex $s$ of (any of the copies of $T^+$ in)~$G$, defined as follows. Let $tt'$ be the edge of the $K_{k+1}$ of which $s$ is a subdividing vertex. Then let $C_s$ be the up-closure of $\{t,s,t'\}$ in~$G$, together with the edges $ts$ and~$st'$. This is a connected subgraph of~$G$, and $G-C_s$ is connected too. The vertex boundary of $C_s$ in $G$ consists of $t$ and~$t'$, each of which is incident with one vertical edges leaving~$C_s$ (to the common predecessor of $t$ and~$t'$ in the copy of $T^+$ containing them) and $k-1$ horizontal such edges. Now consider an end $\omega$ of~$G$. It is represented by a ray $R$ whose vertical edges all go upwards.% \COMMENT{} For every subdividing vertex $s\in R$, the tail $sR$ of $R$ lies in~$C_s$. For every vertical edge $tt^+$ with $t$ not a subdividing vertex,% \COMMENT{} the tail $tR$ of $R$ lies in every $C_s$ whose $s$ is joined to $t$ by a horizontal edge. (There are $k\ge 1$ such vertices~$s$.) Hence every tail of $R$ lies in some~$C_s$, and these $C_s$ form a defining sequence of~$\omega$. It remains to show that every finite subgraph $H$ of $G$ has minimum degree at most~2. Consider a highest vertex~$v$ of~$H$. If $v$ is incident with a horizontal edge $vw\in H$, then either $v$ or $w$ has degree at most~$2$ in~$H$. If not, then $v$ has degree~1 in~$H$. \end{proof} The graph constructed in the proof of Theorem~\ref{xxxUnctbleRestated} can also serve as a counterexample to the naive generalization of Theorem~\ref{xxxCtble}\th(ii) to graphs with uncountably many ends: since no finite subgraph of $G$ has minimum degree~$>2$, there is also no finite subgraph of $G$ that has average degree~$\ge 4$ (see~\cite{refBook}). The graph constructed in Stein\th\cite[Fig.\th 1]{refMayaEndDeg} is also a counterexample to the generalization of Theorem~\ref{xxxCtble}\th(ii) to graphs with any number of ends; see \cite[Lemmas~4.1--2]{refMayaEndDeg}. Our counterexample in Theorem~\ref{xxxUnctble} to the naive extension of Theorem~\ref{xxxCtble} to locally finite graphs with arbitrarily many ends uses only regions $C$ with $G-C$ connected. A~natural stronger requirement, which our example does not satisfy, would be to ask that $N(C)$ be connected: \begin{problem} Does every locally finite graph $G$ of minimum degree at least~$k$ have a finite subgraph of minimum degree at least~$k$ if all its ends have minimum limit degree at least~$k$ witnessed by defining sequences of regions whose neighbourhoods are connected in~$G$? \end{problem} Can the example of Theorem~\ref{xxxUnctbleRestated} be tweaked to give a negative solution to this problem? A~positive solution would be a very nice result indeed. For average degrees, it is easy to modify the example from Theorem~\ref{xxxUnctble} to a counterexample with connected neighbourhoods of regions. Indeed, joining for each subdivided $K_{k+1}$ all its subdividing vertices to the lower neighbour of that $K_{k+1}$ in~$T$ makes the neighbourhoods $N(C_s)$ connected and reduces the average limit degrees of ends to no less than~$\frac{2}{3}k$, but there are still no finite subgraphs of average degree greater than about~4.% \COMMENT{} % % % % % % % % % % % % % % % % % % % % % % % % % % % %\beginsection 4. Positive results for continuum many ends \section{Positive results using topology} In order to prove Theorem~\ref{xxxPos}, we have to view graphs with ends in a topological setting. There is a natural topology on a locally finite graph $G$ with ends that makes it into a compact space extending the 1-complex $G$. This space~$|G|$, the \emph{Freudenthal compactification} of~$G$, is explained in\th\cite{refBook}. All we need here is that every region $C$ of~$G$, together with the ends that live in it and the inner points of edges leaving it, forms an open subset of~$|G|$. We shall denote this open set as~$\hat C$. Every locally finite graph $G$ has a nested set $\C$ of regions $C$ whose corresponding open sets $\hat C\sub |G|$ form a basis of~$|G|$ together with the local open stars around vertices and the open intervals of edges; for example, take the regions induced in $G$ by the up-closures of single vertices in a normal spanning tree. We then say that $\C$ \emph{defines} this basis of~$|G|$. \begin{theorem} \label{xxxPosRestated} Let $G$ be locally finite infinite% \COMMENT{} graph with a nested set $\C$ of regions defining a basis of~$|G|$, and let $k\in\N$ and $q\in\Q$. \begin{enumerate}[\rm (i)] \item If $\delta(G)\ge k$ and $\delta^+_G(C)\ge k$ for every $C\in\C$, then $G$ has a finite subgraph of minimum degree~$\ge k$. \item If $d_G(S)\ge q$ for every large enough finite set $S\sub V(G)$, and ${d^+_G(C) > q}$ for every $C\in\C$, then $G$ has a finite subgraph of average degree~$>q$.% \COMMENT{} \end{enumerate} \end{theorem} \begin{proof} We prove (i); the proof of (ii) is similar, with the same adjustments as in the proof of Theorem~\ref{xxxCtbleRestated}. Let $v$ be a fixed vertex of~$G$, and let $\C'$ be the subset of $\C$ consisting of the sets in $\C$ not containing~$v$. For every end~$\omega$, let $C_\omega$ be the component of $G-v$ in which $\omega$ lives. Since $\C$ defines a basis of~$|G|$ and $\hat C_\omega$ is an open subset of~$|G|$ containing~$\omega$, there is inside~$\hat C_\omega$ a set $\hat C\owns\omega$ with $C\in\C$, and hence $C\in\C'$. So the sets~$\hat C\cap\Omega$ with $C\in\C'$ form an open cover of~$\Omega$, the set of ends of~$G$. Since $\Omega$ is a closed subspace of~$|G|$, and hence compact,% \COMMENT{} we can select from~$\C'$ a finite subset $\{C_1,\dots,C_n\}$ such that $\hat C_1\cup\dots\cup\hat C_n\supe \Omega$. Deleting from this set any $C_i$ contained in another~$C_j$, we may assume that $C_1,\dots,C_n$ are disjoint (using that $\C$ is nested).% \COMMENT{} Since $\hat C_1,\dots,\hat C_n$ are open in~$|G|$, the subspace $X:= |G|\sm (\hat C_1\cup \dots\cup \hat C_n)$ is closed, and hence compact, but contains no end (by the choice of $C_1,\dots,C_n$). As distinct vertices of $G$ can converge only to ends in~$|G|$, this means that $X$ is a finite subgraph of~$G$. (It clearly contains every edge, including its endvertices, of which it contains an inner point.) Since~$v\in X$, it is non-empty. As $\delta_G^+(C_i)\ge k$ for $i=1,\dots,n$, and the vertices of $X$ have at least $k$ neighbours in~$G$, the finite subgraph $H$ of $G$ spanned by $X$ and the vertex boundaries of $C_1,\dots,C_n$ has minimum degree at least~$k$. (We remark that, unlike in the proof of Theorem~\ref{xxxCtbleRestated}, $G$~may have $C_i$--$\,C_j$ edges for $i\ne j$, so the vertex boundaries of the $C_i$ need not lie in~$N(X)$. But any such edges will put their endvertices in $V^+ (C_i)$ and~$V^+ (C_j)$, so they will be edges of~$H$. The conclusion that $\delta(H)\ge k$, therefore, is still correct.) \end{proof} Note that in the proof of Theorem~\ref{xxxPosRestated} we did not use the full assumption that $\C$ defines a basis of~$|G|$, only that there exists a vertex $v\in G$ such that $\Omega$ can be covered by disjoint sets $\hat C$ not containing~$v$ such that $C$ is a good region. It would be possible, of course, to rephrase the theorem in this way. It is also instructive to analyse our counterexample $G$ from the proof of Theorem~\ref{xxxUnctbleRestated} in view of Theorem~\ref{xxxPos}. By Theorem~\ref{xxxPos}, the set $\C$ of regions $C_s$ used in the example for the defining sequences of ends cannot be nested. And indeed, for every horizontal path $tst's't''$ in~$G$ the regions $C_s$ and $C_{s'}$ intersect in the entire up-closure of~$t'$. We could prevent this by taking as $C_s$ only the up-closure of $s$ itself, but then the vertex boundary of $C_s$ would only consist of~$s$, which has only two neighbours outside this set. We finally use Theorem~\ref{xxxPos} to strengthen Theorem~\ref{xxxCtble} by dropping its connectedness requirement on the complements $G-C_n$ of regions used in defining sequences of ends: \begin{corollary} \label{xxxCtbleTop} Let $G$ be a locally finite infinite% \COMMENT{} graph with at most countably many ends, $k\in\N$, and $q\in\Q$. \begin{enumerate}[\rm (i)] \item If $\delta(G)\ge k$ and $\delta^+(\omega)\ge k$ for every end $\omega$ of~$G$, then $G$ has a finite subgraph of minimum degree~$\ge k$. \item If $d_G(S)\ge q$ for every large enough finite set $S\sub V(G)$, and $d^+(\omega) > q$ for every end $\omega$ of~$G$, then $G$ has a finite subgraph of average degree~$>q$. \end{enumerate} \end{corollary} \begin{proof} Once more we prove only~(i), the proof of (ii) being similar. For every end~$\omega$ of~$G$, pick a defining sequence $C_\omega^0\supsetneq C_\omega^1\supsetneq\dots$ witnessing that $\delta^+(\omega)\ge k$. Let $\omega_1,\omega_2,\dots$ be a sequence in which every end of $G$ occurs infinitely often. For $n=1,2,\dots$ let $C_n$ be the first region in the sequence $C_{\omega_n}^0\supsetneq C_{\omega_n}^1\supsetneq\dots$ that has not been chosen as $C_i$ for any $i$. So $C_1,C_2,\dots$ still defines a basis of~$|G|$, and we can apply Theorem~\ref{xxxPos}. \end{proof} Let us conclude with an open problem which has an immediate bearing on the applicability of Theorem~\ref{xxxPos}, but which may be of interest in its own right: \begin{problem} Find natural conditions for a given set of regions of $G$ defining a basis of~$|G|$ to contain nested subset that still defines a basis. \end{problem} % % % % % % % % % % % % % % % % % % % % % % % % % \section*{Acknowledgements} I would like to thank Matthias Hamann for reading an early draft of this paper and suggesting a number of clarifications and corrections. And I would like to thank Maya Stein for alerting me to the fact that her construction in\th\cite{refMayaEndDeg} provides a counterexample to the generalization of Theorem~\ref{xxxCtble}\th(ii) to arbitrary locally finite graphs. % % % % % % % % % % % % % % % % % % % % % % % % % \begin{thebibliography}{99} \bibitem{refSpanningTrees} R.\th Diestel, End spaces and spanning trees, \emph{J. Comb. Theory B} \textbf{96} (2006), 846--854. \bibitem{refBook} R.\th Diestel, {\it Graph theory}, 4th edition, Springer-Verlag 2012. Electronic edition available at \url{http://diestel-graph-theory.com/} \bibitem{refTopSurvey} R.\th Diestel, Locally finite graphs with ends: a topological approach. ArXiv:0912.4213 (2012). \bibitem{refMayaEndDeg} M.\th Stein, Forcing highly connected subgraphs in locally finite graphs, \emph{J. Graph Theory} \textbf{54} (2007), 331--349. \bibitem{refMayaBanff} M.\th Stein, Extremal infinite graph theory, \emph{Discrete Math.} \textbf{311} (2011), 1472--1496. \bibitem{refMayaZamora} M.\th Stein and J.\th Zamora, Forcing large complete minors in infinite graphs, \emph{SIAM J. Discrete Math.} \textbf{27} (2013), 697--707. \bibitem{refHalinEnd} R.{\th}Halin, \"Uber die Maximalzahl frem\-der unendlicher Wege, \emph{Math. Nachr.} \textbf{30} (1965), 63--85. \end{thebibliography} \end{document}