ثابت کنید که تعداد برگها در یک درخت با کمک درجهٔ گره های نابرگ با فرمول $2+\sum_{i=1}^r(\deg v_i-2)$ بدست می آید.

Question

یک درخت را در نظر بگیرید. یک گره از درجهٔ یک را برگ می‌نامیم و گره‌ای که برگ نیست را گرهٔ ناآویزان بنامید. گره‌های ناآویزان را با $v_1$ و $v_2$ و ... و $v_r$ نام‌گذاری کنید که $r$ تعداد گره‌های ناآویزان است. ثابت کنید که تعداد برگ‌ها برابر است با $$2+\sum_{i=1}^r(\deg v_i-2)$$

Answer 1

اگر تعداد راس هایی که از درجه یک هستند را با $ k$ و بقیه را با $ k' $ نمایش دهیم آنگاه $p=k+k' $ که در آن $ p $ تعداد کل رئوس است می دانیم که $2q= \sum deg(v_{i} ) $ و چون درخت داریم لذا $q=p-1 $ پس داریم $$2q=2p-2=2 k+2k'-2= \sum deg(v_{i} )= $$ $$ \sum_{deg(v_{i} )=1} deg(v_{i} )+\sum_{deg(v_{i} ) > 1} deg(v_{i} )=\sum_{deg(v_{i} )=1} 1+\sum_{deg(v_{i} ) > 1} deg(v_{i} )=$$ $$k+\sum_{deg(v_{i} ) > 1} deg(v_{i} )$$ لذا $2 k+2k'-2=k+\sum_{deg(v_{i} ) > 1} deg(v_{i} ) $ پس $ k-2=\sum_{deg(v_{i} ) > 1} deg(v_{i} ) -2k' $ اما می دانیم $\sum_{deg(v_{i} ) > 1} 1=k'$ که با جایگذاری داریم: $$ k-2=\sum_{deg(v_{i} ) > 1} deg(v_{i} ) -2\sum_{deg(v_{i} ) > 1} 1=\sum_{deg(v_{i} ) > 1} (deg(v_{i} )-2)$$ و لذا $k=2+\sum_{deg(v_{i} ) > 1} (deg(v_{i} )-2)$