گراف کامل ‎$n$‎ رأسی ‎$G$‎ را در نظر بگیرید ‎($n>3$)‎ که هر یال آن، وزنی مثبت دارد. می‌دانیم برای هر عدد طبیعی ‎$1\le{}w\le{}\binom{n}{2}$‎، دقیقا یک یال با وزن ‎$w$‎ وجود دارد. کم‌وزن‌ترین یال متصل به هر رأس را، ساق آن رأس می‌نامیم.

بچه‌ی گراف ‎$G$‎، که آن را با ‎$f(G)$‎ نشان می‌دهیم، یک زیرگراف از ‎$G$‎ است. هر یال از ‎$G$‎، در بچه‌اش وجود دارد، اگر ساق دست‌کم یک رأس باشد.

1. بیشینه‌ی تعداد یال‌های ‎$f(G)$‎ چقدر است؟ ‎
2. ثابت کنید اگر ‎$f(G)$‎ درخت شود، یک زیردرخت فراگیر با وزن کمینه از ‎$G$‎ است.
3. ثابت کنید احتمال این که ‎$f(G)$‎ هم‌بند باشد برابر است با

‎\begin{equation*}‎ ‎\frac{(n-2)!^2}{\Pi_{i=2}^{n-2}\left({}\binom{n}{2}-\binom{i}{2}\right)}‎ ‎\end{equation*}‎

• سوال قبل