% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P2.33}{23(2)}{2016}


\usepackage{amsthm,amsmath,enumerate,amssymb}
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\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}

\def\COMMENT{}

\def\NST{normal spanning tree}
\def\TKA{$T K_{\aleph_0}$}
\def\T{T}
\def\dcl(#1){\lceil #1 \rceil}
\def\ucl(#1){\lfloor #1 \rfloor}
\def\sm{\smallsetminus}
\def\H{I}
\def\sube{\subseteq}
  \let\sub=\sube
\def\subne{\subsetneqq}
\def\supe{\supseteq}
\def\wrt{with respect to}
\def\looseproof#1{\bigbreak\noindent {{\bf #1.}}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\title{\bf A simple existence criterion for\\ normal spanning trees}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{Reinhard Diestel\\
\small Mathematisches Seminar\\[-0.8ex]
\small Hamburg University\\[-0.8ex]
\small Germany}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Apr 11, 2016}{Apr 29, 2016}{May 13, 2016}\\
\small Mathematics Subject Classifications: 05C, 05C05, 05C63, 05C75, 05C83}

\begin{document}

\maketitle


\begin{abstract}
\noindent
 Halin proved in 1978 that there exists a normal spanning tree in every connected graph $G$ that satisfies the following two conditions: (i)~$G$~contains no subdivision of a `fat'~$K_{\aleph_0}$, one in which every edge has been replaced by uncountably many parallel edges; and (ii)~$G$ has no $K_{\aleph_0}$ subgraph. We show that the second condition is unnecessary.\par

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} infinite graph, spanning tree, normal, forbidden topological minor
\end{abstract}

\section{Introduction}

A spanning tree of an infinite graph is {\it normal\/} if the endvertices of any chord are comparable in the tree order defined by some arbitrarily chosen root. (In finite graphs, these are their `depth-first search' trees; see~\cite{DiestelBook10noEE} for precise definitions.) Normal spanning trees are perhaps the most important single structural tool for analysing an infinite graph~-- see~\cite{DiestelLeaderBGC} for a typical example, and the exercises in~\cite[Chapter~8]{DiestelBook10noEE} for many more~-- but they do not always exist. The question of which graphs have \NST s thus is an important question.

All countable connected graphs have \NST s~\cite{DiestelBook10noEE}. But not all connected graphs do. For example, if $T$ is a \NST\ of~$G$ and $G$ is complete, then $T$ defines a chain on its vertex set. Hence $T$ must be a single path or ray, and $G$ is countable.

For connected graphs of arbitrary order, there are three characterizations of the graphs that admit a \NST:

\begin{theorem}\label{Characterizations}
The following statements are equivalent for connected graphs~$G$.
\begin{enumerate}[{\rm (i)}]\itemsep=0pt
\item $G$ has a \NST{\/\rm;}
\item $V(G)$ is a countable union of dispersed sets {\rm(}Jung~{\rm\cite{jung69,RDsBanffSurvey});}
\item $|G|$ is metrizable~{\rm\cite{diestelESST};}
\item $G$ contains neither an $(\aleph_0,\aleph_1)$-graph nor an Aronszajn-tree graph as a minor~{\rm\cite{DiestelLeaderNST}.}
\end{enumerate}
\end{theorem}

\goodbreak

\noindent
Here, a set of vertices in $G$ is {\it dispersed\/} if every ray can be separated from it by some finite set of vertices. (The levels of a \NST\ are dispersed; see~\cite{DiestelBook10noEE}.) The dispersed vertex sets in a graph~$G$ are precisely those that are closed in the topological space~$|G|$ of~(iii), which consists of $G$ and its ends~\cite{diestelESST}. The space $|G|$ will not concern us in this note, so we refer to~\cite{diestelESST} for the definition of the topology on~$|G|$. But we shall use the equivalence of (i) and~(iv) in our proof, and the forbidden minors mentioned in~(iv) will be defined in Section~\ref{secProof}.

Despite the variety in Theorem~\ref{Characterizations}, it can still be hard in practice to decide whether a given graph has a \NST.%
   \footnote{In particular, the two types of graph mentioned in~(iv) are not completely understood; see~\cite{DiestelLeaderNST} for the~-- quite intriguing~-- problem of how to properly understand (or meaningfully classify) the $(\aleph_0,\aleph_1)$-graphs.}
   In most applications, none of these characterizations is used, but a simpler sufficient condition due to Halin. This condition, however, is much stronger, and hence does not always hold even if a \NST\ exists. It is the purpose of this note to show that this condition can be considerably weakened.

\section{The result}\label{secResults}

Halin's~\cite{halin78} most-used sufficient condition for the existence of a \NST\ in a connected graph is that it does not contain a $\T K_{\aleph_0}$. This is usually easier to check than the conditions in Theorem~\ref{Characterizations}, but it is also quite a strong assumption. However, Halin~\cite{halin78} also proved that this assumption can be replaced by the conjunction of two independent much weaker assumptions:
 %
\begin{itemize}\itemsep=0pt
\item $G$ contains no {\it fat $\T K_{\aleph_0}$}: a subdivision of the multigraph obtained from a $K_{\aleph_0}$ by replacing every edge with $\aleph_1$ parallel edges;
\item $G$ contains no $K_{\aleph_0}$ (as a subgraph).
\end{itemize}
We shall prove that the second condition is unnecessary:

\begin{theorem}\label{Main}
Every connected graph not containing a fat $\T K_{\aleph_0}$ has~a~\NST.
\end{theorem}
We remark that all the graphs we consider are simple, including our fat $\T K_{\aleph_0}$s. When we say, without specifying any graph relation, that a graph $G$ {\it contains\/} another graph~$H$, we mean that $H$ is isomorphic to a subgraph of~$G$. Any other undefined terms can be found in~\cite{DiestelBook10noEE}.


\section{The proof}\label{secProof}

Our proof of Theorem~\ref{Main} will be based on the equivalence (i)$\leftrightarrow$(iv) in Theorem~\ref{Characterizations}, so let us recall from~\cite{DiestelBook10noEE} the terms involved here.

An {\it Aronszajn tree\/} is a poset $(T,\le)$ with the following properties:%
   \footnote{Unlike the perhaps better known Suslin trees~-- Aronszajn trees in which even every anti\-chain must be countable~-- Aronszajn trees can be shown to exist without any set-theoretic assumptions in addition to~ZFC.} 

\begin{itemize}\itemsep=0pt
\item $T$ that has a least element, its {\it root\/};
\item the down-closure of every point in $T$ is well-ordered;
\item $T$ is uncountable, but all chains and all levels in $T$ are  countable.
\end{itemize}
   %
Here, the {\it down-closure\/} $\dcl(t)$ of a point $t\in T$ is the set $\{\,x\mid x\le t\,\}$; its {\it up-closure\/} is the set $\ucl(t) := \{\,y\mid t\le y\,\}$.\vadjust{\penalty-500}
More generally, if $x<y$ we say that $x$ lies {\it below\/} $y$ and $y$ {\it above\/}~$x$. The {\it height\/} of a point $t\in T$ is the order type of the chain $\dcl(t)\sm\{t\}$, and the {\it levels\/} of $T$ are its maximal subsets of points of equal height.

An {\it Aronszajn-tree graph\/} or {\it AT-graph\/}, is a graph~$G$ on whose vertex set there exists an Aronszajn tree $T$ such that

\begin{itemize}\itemsep=0pt
\item the endvertices of every edge of $G$ are comparable in~$T$;
\item for all $x<y$, the vertex $y$ has a neighbour $x'$ such that $x\le x'<y$.
\end{itemize}
   %
The second condition says that each vertex is joined cofinally to the vertices below it. The idea behind this is that if we were to construct any order tree $T$ on $V(G)$ satifying the first condition, a tree satisfying also the second condition would be one that minimizes the level of each vertex.%
   \COMMENT{}

Note that {\it intervals\/} in~$T$, sets of the form $\{\,t\mid x\le t < y\,\}$ for some given points $x<y$, span connected subgraphs in~$G$. This is because every ${t > x}$ has a neighbour $t'$ with $x\le t' < t$, by the second condition, and hence the interval contains for each of its elements~$t$ the vertices of a $t$--$x$ path in~$G$. Similarly, $G$~itself is connected, because every vertex can be linked to the unique root of~$T$.\looseness=-1

An {\it $(\aleph_0,\aleph_1)$-graph with bipartition $(A,B)$\/} is a bipartite graph with vertex classes $A$ of size~$\aleph_0$ and $B$ of size~$\aleph_1$ such that every vertex in $B$ has infinite degree.

Replacing the vertices $x$ of a graph $X$ with disjoint connected graphs~$H_x$, and the edges $xy$ of $X$ with non-empty sets of $H_x$--$\,H_y$ edges, yields a graph that we shall call an~$\H X$ (for `inflated~$X$'). More formally, a graph {\it $H$ is an~$\H X$} if its vertex set admits a partition
${\{\,V_x\mid x\in V(X)\,\}}$ into connected subsets~$V_x$ such that distinct vertices $x,y\in X$ are adjacent in $X$ if and only if $H$ contains a $V_x$--$V_y$ edge. The sets $V_x$ are the {\it branch sets of the~$\H X$\/}. Thus, $X$~arises from $H$ by contracting the subgraphs~$H_x$, without deleting any vertices or edges (other than loops or parallel edges arising in the contraction). A~graph $X$ is a {\it minor\/} of a graph $G$ if $G$ contains an~$\H X$ as a subgraph. See~\cite{DiestelBook10noEE} for more details.

For our proof of Theorem~\ref{Main} from Theorem~\ref{Characterizations}\ (i)$\leftrightarrow$(iv) it suffices to show the following:

\begin{equation}\tag{\ensuremath{*}}
\begin{minipage}[c]{0.8\textwidth}\em
Every $\H X$, where $X$ is either an $(\aleph_0,\aleph_1)$-graph or an AT-graph, contains a fat $\T K_{\aleph_0}$ (as a subgraph).
\end{minipage}
\end{equation}

\medskip\noindent
The rest of this section is devoted to the proof of~$(*)$.

\begin{lemma}\label{AAproperties}
Let $X$ be an $(\aleph_0,\aleph_1)$-graph, with bipartition $(A,B)$ say.
\begin{enumerate}[{\rm (i)}]\itemsep=0pt
\item $X$ has an $(\aleph_0,\aleph_1)$-subgraph $X'$ with bipartition into $A'\sub A$ and ${B'\sub B}$ such that every vertex in $A'$ has uncountable degree in~$X'$.
\item For every finite set $F\sub A$ and every uncountable set $U\sub B$, there exists a vertex $a\in A\sm F$ that has uncountably many neighbours in~$U$.
\end{enumerate}
\end{lemma}

\goodbreak

\begin{proof}
(i) Delete from $X$ all the vertices in~$A$ that have only countable degree, together with their neighbours in~$B$. Since this removes only countably many vertices from~$B$, the remaining set~$B'\sub B$ is still uncountable.\vadjust{\penalty-2000} Every $b'\in B'$ has all its $X$-neighbours in the set $A'$ of the vertices in~$A$ that we did not delete, as otherwise $b'$ would have been deleted too. Thus, $b'$~still has infinite degree in the subgraph $X'$ of $X$ induced by $A'$ and~$B'$. In particular, $A'$~is still infinite, and $X'$ is the desired $(\aleph_0,\aleph_1)$-subgraph of~$X$.

(ii) If there is no vertex $a\in A\sm F$ as claimed, then each vertex $a\in A\sm F$ has only countably many neighbours in~$U$. As $A\sm F$ is countable, this means that $U\sm N(A\sm F)\ne\emptyset$. But every vertex in this set has all its neighbours in~$F$, and thus has finite degree. This contradicts our assumption that $X$~is an $(\aleph_0,\aleph_1)$-graph.
\end{proof}

\begin{lemma}\label{AAfat}
Let $X$ be an $(\aleph_0,\aleph_1)$-graph with bipartition $(A,B)$. Let $A'\sub A$ be infinite and such that for every two vertices $a,a'$ in $A'$ there is some uncountable set $B(a,a')$ of common neighbours of $a$ and~$a'$%
   \COMMENT{}
   in~$B$. Then $A'$ is the set of branch vertices of a fat~\TKA\ in $X$ whose subdivided edges all have the form $aba'$ with $b\in B(a,a')$.
\end{lemma}

\begin{proof}
We have to find a total of $\aleph_0^2\cdot\aleph_1 = \aleph_1$ independent paths in $X$ between vertices in~$A'$. Let us enumerate these desired paths as $(P_\alpha)_{\alpha < \omega_1}$; it is then easy to find them recursively on~$\alpha$, keeping them independent. 
   \COMMENT{}
\end{proof}

\begin{lemma}\label{IAAfat}

Every $\H X$, where $X$ is an $(\aleph_0,\aleph_1)$-graph, contains a fat $\T K_{\aleph_0}$.
\end{lemma}

\begin{proof}
Let $H$ be an $\H X$ for an $(\aleph_0,\aleph_1)$-graph $X$ with bipartition $(A,B)$, with branch sets $V_x$ for vertices $x\in X$. Replacing $X$ with an appropriate $(\aleph_0,\aleph_1)$-subgraph $Y$ (and $H$ with the corresponding~$\H Y\sub H$) if necessary, we may assume by Lemma~\ref{AAproperties} (i) that every vertex in~$A$ has uncountable degree in~$X$. We shall find our desired fat \TKA\ in~$H$ as follows.

We construct, inductively, an infinite set $A' = \{a_0,a_1,\dots\}\sub A$ such that, for each $a_i\in A'$, there is an uncountable subdivided star $S(a_i)\sub H[V_{a_i}]$ whose leaves send edges of~$H$ to the branch sets of distinct vertices $b\in B$. The sets $B_i$ of these~$b$%
   \COMMENT{}
   will be nested as $B_0\supe B_1\supseteq\dots$. We shall then apply Lemma~\ref{AAfat} to find a fat \TKA\ in~$X$, and translate this to the desired fat \TKA\ in~$H$.

Pick $a_0\in A$ arbitrarily. For each of the uncountably many neighbours $b$ of $a_0$ in $B$ we can find a vertex $v_b\in V_b$ that sends an edge of~$H$ to~$V_{a_0}$. For every~$b$, pick one neighbour $u_b$ of $v_b$ in~$V_{a_0}$. Consider a minimal connected subgraph $H_0$ of~$H[V_{a_0}]$ containing all these vertices~$u_b$, and add to it all the edges~$u_b v_b$ to obtain the\vadjust{\penalty-200} graph~$T = T(a_0)$. By the minimality of~$H_0$,

\begin{equation}\tag{\ensuremath{1}}
\begin{minipage}[c]{0.8\textwidth}\em
$T$~is a tree in which every edge lies on a path between two vertices of the form~$v_b$.
\end{minipage}
\end{equation}

Since there are uncountably many~$b$%
   \COMMENT{}
   and their $v_b$ are distinct, $T$~is uncountable and hence has a vertex $s_0$ of uncountable degree. For every edge $e$ of $T$ at~$s_0$ pick a path in $T$ from $s_0$ through $e$ to some~$v_b$; this is possible by~(1). Let $S(a_0)$ be the union of all these paths. Then $S(a_0)$ is an uncountable subdivided star with centre~$s_0$ all whose non-leaves lie in~$V_{a_0}$ and whose leaves lie in the branch sets $V_b$ of distinct vertices $b\in B$. Let $B_0\sub B$ be the (uncountable) set of these~$b$, and rename the vertices $v_b$ with $b\in B_0$ as~$v_b^0$.

Assume now that, for some $n\ge 1$, we have picked distinct vertices $a_0,\dots,a_{n-1}$ from~$A$ and defined uncountable subsets $B_0\supe \dots\supe B_{n-1}$ of~$B$ so that each $a_i$ is adjacent in $X$ to every vertex in~$B_i$. By Lemma~\ref{AAproperties} (ii) there exists an $a_n\in A\sm \{a_0,\dots,a_{n-1}\}$ which, in~$X$, has uncountably many neighbours in~$B_{n-1}$. As before, we can find an uncountable subdivided star $S(a_n)$ in~$H$ whose centre $s_n$ and any other non-leaves lie in $V_{a_n}$ and whose leaves $v_b^n$ lie in the branch sets $V_b$ of (uncountably many) distinct vertices $b\in B_{n-1}$. We let $B_n$ be the set of those~$b$. Then $B_n$ is an uncountable subset of~$B_{n-1}$, and $a_n$~is adjacent in~$X$ to all the vertices in~$B_n$, as required for~$n$ by our recursion.

By construction, every two vertices $a_i,a_j$ in $A' := \{a_0, a_1,\dots\}$ have uncountably many common neighbours in~$B$: those in $B_j$ if $i<j$. By Lemma~\ref{AAfat} applied with $B(a_i,a_j):= B_j$ for $i<j$, we deduce that $A'$~is the set of branch vertices of a fat~\TKA\ in $X$ whose subdivided edges $a_i\dots a_j$ with $i<j$ have the form $a_i b a_j$ with $b\in B_j$.%
   \COMMENT{}
Replacing each of these paths $a_i b a_j$ with the concatenation of paths $s_i\dots v_b^i\sub S(a_i)$ and $v_b^i\dots v_b^j\sub H[V_b]$ and $v_b^j\dots s_j\sub S(a_j)$, we obtain a fat \TKA\ in~$H$ with  $s_0,s_1,\dots$ as branch vertices. (It is important here that $b$ is not just any common neighbour of $a_i$ and~$a_j$ but one in~$B_j$: only then do we know that $S(a_i)$ and $S(a_j)$ both have a leaf in~$V_b$.)
\end{proof}

Let us now turn to the case of $(*)$ where $X$ is an AT-graph. As before, we shall first prove that $X$ itself contains a fat \TKA, and later refine this to a fat \TKA\ in any~$\H X$. In this second step we shall be referring to the details of the proof of the lemma below, not just to the lemma itself.

\begin{lemma}\label{ATfat}
Every AT-graph contains a fat~\TKA.
\end{lemma}

\begin{proof}
Let $X$ be an AT-graph, with Aronszajn tree $T$, say. Let us pick the branch vertices $a_0, a_1,\dots $ of our desired \TKA\ inductively, as follows.

Let $t_0$ be the root of $T_0:= T$, and $X_0 := X$. Since $X_0$ is connected,%
   \COMMENT{}
  it has a vertex $a_0$ of uncountable degree. Uncountably many of its neighbours lie above it in~$T_0$, because its down-closure is a chain and hence countable, and all its neighbours are comparable with it (by definition of an AT-graph). As levels in $T_0$ are countable, $a_0$~has a successor~$t_1$ in~$T_0$ such that uncountably many $X_0$-neighbours of $a_0$ lie above~$t_1$; let $B_0$ be some uncountable set of neighbours of~$a_0$ in~$\ucl(t_1)_{T_0}$. (We shall specify $B_0$ more precisely later.)

Let $T_1$ be the down-closure of $B_0$ in~$\ucl(t_1)_{T_0}$. Since $T_1$ is an uncountable subposet of $T_0$ with least element~$t_1$, it is again an Aronszaijn tree, and the subgraph $X_1$ it induces in $X_0$ is an AT-graph with respect to~$T_1$.

Starting with $t_0$, $T_0$ and $X_0$ as above, we may in this way select for $n=0,1,\dots$ an infinite sequence $T_0\supe T_1\supe\dots$ of Aronszajn subtrees of $T$ with roots $t_0 < t_1 <\dots$ satisfying the following:
   \begin{itemize}\itemsep=0pt
  \item $X_n:= X[T_n]$ is an AT-graph \wrt~$T_n$;
  \item the predecessor $a_n$ of $t_{n+1}$ in~$T_n$ has an uncountable set $B_n$ of $X_n$-neighbours above $t_{n+1}$ in~$T_n$;
  \item $T_{n+1} = \ucl(t_{n+1})_{T_n} \cap \dcl(B_n)_{T_n}$.
   \end{itemize}

\goodbreak

\noindent
By the last item above, there exists for every $b\in T_{n+1}$ a vertex $b'\in B_n\cap \ucl(b)$ (possibly $b'=b$). Applied to vertices $b$ in $B_{n+1}\sub T_{n+1}$ this means that, inductively,

\begin{equation}\tag{\ensuremath{2}}
\begin{minipage}[c]{0.8\textwidth}\em
Whenever $i<j$, every vertex in $B_j$ has some vertex of $B_i$ in its up-closure.%
   \COMMENT{} 
\end{minipage}
\end{equation}

\smallskip
Let us now make $a_0, a_1,\dots$ into the branch vertices of a fat \TKA\ in~$X$. As earlier, we enumerate the desired subdivided edges as one $\omega_1$-sequence, and find independent paths $P_\alpha\sub X$ to serve as these subdivided edges recursively for all $\alpha < \omega_1$. When we come to construct the path~$P_\alpha$, beween $a_i$ and $a_j$ with $i<j$ say, we have previously constructed only the countably many paths~$P_\beta$ with $\beta<\alpha$. The down-closure $D_\alpha$ in~$T$ of all their vertices and all the $a_n$ is a countable set, since the down-closure of each vertex is a chain in~$T$ and hence countable. We can thus find a vertex $b\in B_j$ outside~$D_\alpha$, and a vertex $b'\ge b$ in~$B_i$ by~(2). The interval of $T$ between $b$ and $b'$ thus avoids~$D_\alpha$, and since it is connected in $X$ it contains the vertices of a $b'$--$b$ path $Q_\alpha$ in $X-D_\alpha$. We choose $P_\alpha := a_i b' Q_\alpha b a_j$ as the $\alpha$th subdivided edge for our fat~\TKA\ in~$X$.
\end{proof}

\begin{lemma}\label{IATfat}
Every $\H X$, where $X$ is an AT-graph, contains a fat $\T K_{\aleph_0}$.
\end{lemma}

\begin{proof}
Let $H$ be an $\H X$ with branch sets $V_x$ for vertices $x\in X$, where $X$ is an AT-graph \wrt\ an Aronszajn tree $T$. Rather than applying Lemma~\ref{ATfat} to $X$ formally, let us re-do its proof for~$X$. We shall choose the sets~$B_n$ more carefully this time, so that we can turn the fat \TKA\ found in $X$ into one in~$H$.

Given~$n$, the set $B_n$ chosen in the proof of Lemma~\ref{ATfat} was an arbitrary uncountable set of upper neighbours of $a_n$ in~$T_n$ above some fixed successor $t_n$ of~$a_n$. We shall replace $B_n$ with a subset of itself, chosen as follows. For every $b\in B_n$, pick a vertex $v_b^n\in V_b$ that sends an edge of $H$ to a vertex~$u^n_b\in V_{a_n}$.%
  \COMMENT{}
  As in the proof of Lemma~\ref{IAAfat}, there is a subdivided uncountable star $S_n$ in $H$ whose leaves are among these~$v_b^n$ and all whose non-leaves, including its centre~$s_n$, lie in~$V_{a_n}$. Let us replace $B_n$ with its (uncountable) subset consisting of only those~$b$ whose $v_b^n$ is a leaf of~$S_n$.

Let $K\sub X$ be the fat \TKA\ found by the proof of Lemma~\ref{ATfat} for these revised sets~$B_n$. In order to turn $K$ into the desired \TKA\ in~$H$, we replace its branch vertices $a_n$ by the centres $s_n$ of the stars~$S_n$, and its subdivided edges $P_\alpha = a_i b' Q_\alpha b a_j$ between branch vertices $a_i, a_j$ by the concatenation of paths $s_i\dots v^i_{b'}\sub S_i$ and $Q'_\alpha = v_{b'}^i\dots v_{b}^j$ and $v^j_{b}\dots s_j\sub S_j$, where $Q'_\alpha$ is a path in $H$ expanded from~$Q_\alpha$, i.e.\ whose vertices lie in the branch sets of the vertices of~$Q_\alpha$. These paths $P'_\alpha$ are internally disjoint for distinct~$\alpha$, because the $P_\alpha$ were internally disjoint.
 \end{proof}

\looseproof{Proof of Theorem~\ref{Main}}
Let $G$ be a connected graph without a \NST; we show that $G$ contains a fat~\TKA. By Theorem~\ref{Characterizations}, $G$~has an $X$-minor such that $X$ is either an $(\aleph_0,\aleph_1)$-graph or an Aronszajn-tree graph. Equivalently, $G$~has a subgraph $H$ that is an~$\H X$, with $X$ as above. By Lemmas~\ref{IAAfat} and~\ref{IATfat}, this subgraph~$H$, and hence~$G$, contains a fat~\TKA.\qed


\begin{thebibliography}{99}

\bibitem{diestelESST}
R.~Diestel.
\newblock End spaces and spanning trees.
\newblock {\em J.~Combin.\ Theory (Series B)}, 96:846--854, 2006.

\bibitem{DiestelBook10noEE}
R.~Diestel.
\newblock {\em {Graph Theory}}.
\newblock Springer, 4th edition, 2010.

\bibitem{RDsBanffSurvey}
R.~Diestel.
\newblock Locally finite graphs with ends: a topological approach.
\newblock {\em Discrete Math.}, 310--312:~2750--2765 (310); 1423--1447 (311);
  21--29 (312), 2010--11.
\newblock arXiv:0912.4213.

\bibitem{DiestelLeaderBGC}
R.~Diestel and I.~Leader.
\newblock A proof of the {B}ounded {G}raph {C}onjecture.
\newblock {\em Invent.\ math.}, 108:131--162, 1992.

\bibitem{DiestelLeaderNST}
R.~Diestel and I.~Leader.
\newblock Normal spanning trees, {A}ronszajn trees and excluded minors.
\newblock {\em J.\ London Math.\ Soc.}, 63:16--32, 2001.

\bibitem{halin78}
R.~Halin.
\newblock Simplicial decompositions of infinite graphs.
\newblock In B.Bollob\'as, editor, {\em Advances in Graph Theory, Annals of
  Discrete Mathematics}, volume~3. North-Holland, 1978.

\bibitem{jung69}
H.A. Jung.
\newblock Wurzelb{\"a}ume und unendliche {W}ege in {G}raphen.
\newblock {\em Math.\ Nachr.}, 41:1--22, 1969.

\end{thebibliography}


\end{document}
