g Suppose that result holds for n=k-1 今Forn=k,8(T)≥1 o There is a vertex that has degree one. The vertex is denoted by u. ie d(u=l 4 Why? 2e≥2k,ie.e≥k(e=n-1=k-1), contradiction g We has a new graph T' which is obtained from t by removing the vertex u and incident with edge u,v By the inductive hypothesis, T doesn't contain any simple circuit. Thus t doesn't contain any simple circuit❖ Suppose that result holds for n=k-1 ❖ For n=k, (T)1 ❖ There is a vertex that has degree one. The vertex is denoted by u. i.e d(u)=1. ❖ Why? ❖ 2e2k, i.e. ek( e=n-1=k-1), contradiction ❖ We has a new graph T’ which is obtained from T by removing the vertex u and incident with edge {u,v} ❖ By the inductive hypothesis, T' doesn't contain any simple circuit. Thus T doesn't contain any simple circuit