$k$-connected graphs containing trees

Question

I've encountered the following problem in the book "Graphs and Digraphs" and I'm not sure how to do it.

Show that every $k$-connected graph contains any tree of order $k+1$ as a subgraph.

Answer 1

As already stated by Yuval, induction works fine.

We use induction on $k$. Remember that $k$-connectedness requires $k+1$ vertices and that (by convention and/or by a suitable choice of the definition of $k$-connectedness) $K_n$ is $n-1$-connected.

Induction base ($k=1$): $G$ is connected and has more than one vertex, so it has an edge. This means that it embeds the one and only tree on 2 vertices. (Note that we can even allow $k=0$, provided we do not allow empty graphs or at least define the empty graph to be not $0$-connected).

Induction step: $k>1$ and the statement proven for smaller values. Let $T$ be a tree of order $k+1$. Since $k>1$ $T$ has a leaf $v$. Let $u$ be its neighbour. We can embed $T-v$ in $G$ by the induction hypothesis. Let $f:T-v\rightarrow G$ be the embedding.

$T-v$ has only $k$ vertices, so it has only $k-1$ vertices different from $u$. Since $f(u)$ has $k$ neighbours (because $G$ is $k$-connected) it has at least one `free' neighbour to which we can map $v$.