= Solution
For the first assertion, use the standard nonempty finite-graph convention. Choose a longest simple path in an <acyclic graph>. Its endpoint can have no neighbour outside the path, or the path could be extended; it can have no neighbour farther back than the adjacent path vertex, or there would be a cycle. Its degree is therefore at most one. The qualification matters for infinite graphs: a two-sided infinite path is acyclic and every vertex has degree two.
A finite tree with $n>1$ has a leaf by this argument and connectedness. Removing it and its one edge leaves a tree with $n-1$ vertices. Induction from the one-vertex tree proves \b[a tree of order $n$ has $n-1$ edges]. Conversely, a finite connected graph has a spanning tree: begin with one vertex and repeatedly add an edge to a new vertex until every vertex is reached. This creates no cycle and uses $n-1$ edges. If the original graph has exactly that many edges, it equals its spanning tree and is itself a tree.
To embed a tree $T$ of order $t$, root it and list its vertices so every nonroot vertex follows its parent. Embed the root at any vertex of $G$. When embedding a new vertex, at most $t-2$ neighbours of its parent's image are already used, while that image has degree at least $t-1$. An unused neighbour exists and can be chosen. This constructs an injective edge-preserving copy of $T$, so
$$
\boxed{\delta(G)\ge t-1\ \Longrightarrow\ T\subseteq G.}
$$
For $t\ge2$, the complete graph $K_{t-1}$ has minimum degree $t-2$ but too few vertices to contain $T$. Thus \b[the degree bound cannot be lowered in general]. A subgraph copy need not be induced; extra edges in $G$ do not obstruct the construction.
Back to article page
