Can someone give me a proof sketch for this:
Let $\mathscr{P}\_n$ be the set of all graphs which do not contain a path on $n$ vertices as a subgraph. Define the type of a graph inductively as: the type of the single vertex graph is $1$. The type of a graph $G$ is at most $n$ if there exists a vertex $v\in G$ such that every connected component of $G\setminus\{v\}$ has type at most $n-1$. Denote the set of graphs of type at most $n$ by $\mathscr{T}\_n$.


**Claim.** $\mathscr{P}\_n \subseteq \mathscr{T}\_n$.



A claim from "Graph minors - a survey" by Robertson and Seymour
This is trickier than it seems. 


**Definition.** Let $\mathscr{R}\_n$ denote the set of all *connected* graphs $G$ for which there is a vertex $v\in G$ such that $G$ contains no path on $n$ vertices starting at $v$. 


**Proposition 1.** For $n\geq 2$, we have $\mathscr{R}\_n\subseteq\mathscr{T}\_{n-1}$.


**Proof.** We prove this by induction on $n$. For $n=2$, the statement says that a single vertex graph lies in $\mathscr{T}\_1$, which is true. Assume now that $n\geq 3$, and the statement holds for $n-1$ in place of $n$. Let $G\in\mathscr{R}\_n$. By definition, there is a vertex $v\in G$ such that $G$ contains no path on $n$ vertices starting at $v$. Let $H$ be a connected component of $G\setminus\{v\}$. As $G$ is connected, there exists a vertex $w\in H$ such that $\{v,w\}$ is an edge in $G$. Clearly, $H$ contains no path on $n-1$ vertices starting at $w$, because together with the edge $\{v,w\}$ it would form a path on $n$ vertices starting at $v$. Hence $H\in\mathscr{R}\_{n-1}$, and therefore $H\in\mathscr{T}\_{n-2}$ by the induction hypothesis. This shows, by definition, that $G\in\mathscr{T}\_{n-1}$. 


**Proposition 2.** For $n\geq 1$, we have $\mathscr{P}\_n\subseteq\mathscr{T}\_n$.


**Proof.** We can assume that $n\geq 2$, because $\mathscr{P}\_1=\emptyset$. Let $G\in\mathscr{P}\_n$ be arbitrary, and fix a vertex $v\in G$. If $H$ is any connected component of $G\setminus\{v\}$, then clearly $H\in\mathscr{R}\_n$, hence also $H\in\mathscr{T}\_{n-1}$ by Proposition 1. This shows, by definition, that $G\in\mathscr{T}\_n$.


