A claim from “Graph minors - a survey” by Robertson and Seymour

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$.

• Isn't this straightforward induction? – Peter Shor May 10 '15 at 19:19
• @PeterShor: I did not find it that straightforward, have a look at my proof below. – GH from MO May 10 '15 at 20:57
• Notice that there exist graphs such that the intersection of all possible longest paths is empty. Thus deleting a vertex from such a graph does not drop its P_n number. – Thinniyam Srinivasan Ramanatha May 11 '15 at 4:08

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$.

• Lovely - and unexpectedly tricky! – Dominic van der Zypen May 11 '15 at 6:45