特别提醒：图论中有 很多小的术语（概念）， 一定要理解和记忆住
特别提醒：图论中有 很多小的术语(概念)， 一定要理解和记忆住
以下概念的区分 。Subgraph、proper subgraph ·Spanning subgraph、induced subgraph 。Walk ·Trail、Path、 。Circuit、Circle ·Distance、geodesic、diameter
以下概念的区分 • Subgraph、proper subgraph • Spanning subgraph、induced subgraph • Walk • Trail、Path、 • Circuit、Circle • Distance、geodesic、diameter
Theorem 1.6 If a graph G contains a u-v walk of length l,then G contains a u-v path of length at most I. Proof.Among all u-vwalks in G,let P=(u=40,1,,uk=V) 还有其它证 be a u-vwalk of smallest length k.Therefore,k sI.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,sayufor some iandjwithssk.If we then delete the verticesu 2.from P,we arrive at the u-vwalk 图中定理的证 (u=0,1,,1-1,4=j,uj+1,…,4以=V） 明，多用如此 whose length is less than k,which is impossible.Therefore,as claimed,P is a u-vpath 的反证法、构 of length k≤l ■ 造法
图中定理的证 明，多用如此 的反证法、构 造法 v 还有其它证 明方法吗？