3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I see. "shortest" is the key. Thank you very much! $\endgroup$ – Zhou Heng Aug 7 '13 at 5:55
0
$\begingroup$

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.

$\endgroup$

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.