Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.