Let $n$ be a positive integer and $K$ be the set of all the $2$-elements subsets of $\{1,2,...,n\}$, then $|K|= \binom{n}{2}$. Define $$S=\left\{P\subseteq K:\bigcup_{I\in P}I=\{1,2,...,n\}\right\}.$$
For any $P\in S$,define a simple graph $G_P$:
$(1)$ $G_P$ has $n+|P|$ vertices and $V(G_P)=\{v_i:i=1,2,...,n\}\bigcup\{w_{\{j,k\}}:\{j,k\}\in P\}$;
$(2)$ $E(G_P)=\{v_iv_{i+1}:i=1,2,...,n-1\}\bigcup\{w_{\{j,k\}}v_j,w_{\{j,k\}}v_k:\{j,k\}\in P\}$.
Obviously there is a path between $v_1$ and $v_n$ in $G_P$ whose length is $n-1$. I guess for any $P\in S$, there must exist another path between $v_1$ and $v_n$ in $G_P$ whose length is larger than $n-1$; is it true?
