Theorem 1.6 If a graph G contains a u-v walk of length l,then G contains a u-l path of length at most I. Proof.Among all u-v walks in G,let P=(u=0,1,,k= 图中定 be a u-vwalk of smallest length k.Therefore,k s I.We claim that P is a u-v path. Assume,to the contrary,that this is not the case.Then some vertex of Gmust be repeated 理的证 in P,sayu=;for some iandjwithik.If we then delete the verticesu 明，多 from P,we arrive at the u-vwalk 用如此 的构造 (=0,41,,41-1,4=j,4j+1,…,4= 法 whose length is less than k,which is impossible.Therefore,as claimed,P is a uvpath of lengthk≤l. ■图中定 理的证 明，多 用如此 的构造 法