5
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Isn't this straightforward induction? $\endgroup$
    – Peter Shor
    May 10, 2015 at 19:19
  • $\begingroup$ @PeterShor: I did not find it that straightforward, have a look at my proof below. $\endgroup$
    – GH from MO
    May 10, 2015 at 20:57
  • $\begingroup$ 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. $\endgroup$ May 11, 2015 at 4:08

1 Answer 1

8
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ Lovely - and unexpectedly tricky! $\endgroup$ May 11, 2015 at 6:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.