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$
  • $\begingroup$ Isn't this straightforward induction? $\endgroup$ – Peter Shor May 10 '15 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 '15 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$ – Thinniyam Srinivasan Ramanatha May 11 '15 at 4:08
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$
  • 2
    $\begingroup$ Lovely - and unexpectedly tricky! $\endgroup$ – Dominic van der Zypen May 11 '15 at 6:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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