Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I met with a problem in the proof of Theorem 1.3 in page 14 of "Combinatorics and Graph Theory", 2nd Edition, John Harris, Jeffry L. Hirst, Michael Mossinghoff. The proof is excerpted as follows:

enter image description here

My problem comes from the claim $v'=v_i=w_i$ underlined with a red line. Why $v_i$ and $w_i$ must have the same subscript $i$? Thank you.

share|improve this question

2 Answers 2

up vote 3 down vote accepted

Suppose $v'=v_i=w_j$ with $i\ne j$. We may assume that $i<j$. Then the path $v=v_0,v_1,\ldots,v_i=w_j,w_{j+1},w_{j+2},\ldots,w_{2t}=x'$ is a shorter path from $v$ to $x'$, which is a contradiction, as $P_2$ was supposed to be minimal.

share|improve this answer
I see. "shortest" is the key. Thank you very much! –  Zhou Heng Aug 7 '13 at 5:55

Clearly $v = v_{0} = w_{0}$ is common in $P_{1}$ and $P_{2}$. Now starting from $0$ there must be a first integer $j$ where the paths $P_{1}$, $P_{2}$ diverge and the vertices before $j$ i.e. $v_{j - 1}$ and $w_{j - 1}$ must be same so that $i = j - 1$ and clearly both $v$ and $w$ should have same subscript $i$ because the starting index for common vertex in $P_{1}$, $P_{2}$ is same.

share|improve this answer

Your Answer


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

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