# the length of paths in a specific graph

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=\{P\subseteq K:\bigcup_{I\in P}I=\{1,2,...,n\}\}.$$

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 has 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？

-
If you suppose that P is (or contains) a perfect matching, then this should follow from Smith's theorem which claims that in any cubic graph G there must be an even number of Hamiltonian cycles through any fixed edge uv. Probably the general version can also be reduced to this case. – domotorp Dec 18 '13 at 7:05
Yes，I know that and I have tried hard to do what you said.But I can not work it out and I believe if my guess is right,there must exist some different method for this problem. – user40096 Dec 18 '13 at 8:28
If I understand correctly, you are just considering all graphs on $n$ vertices with minimum degree 1, then subdividing each edge and adding a path through all original vertices? – nvcleemp Dec 18 '13 at 8:35
I am sorry,nvcleemp.I do not quite understand what you mean.Can you explain your meaning in detail? – user40096 Dec 19 '13 at 0:52
By now I am convinced that this statement might be pretty hard. See related problems at math.uiuc.edu/~west/regs/extraham.html – domotorp Dec 21 '13 at 15:08