Граф

[asdf]

Да се докаже, че ако в един граф G(V,E),|V|=n и за всяко [tex]v_{i} \in V[/tex] е изпълнено [tex]d(v_{i}) \ge \frac{n-1}{2}[/tex], то графът е свързан.

[Реклама]

[nikko1]

Лесно става. Допускаш, че всеки връх е свързан с поне [tex]\frac{n-1}{2}[/tex] ребра, но съществуват 2 върха [tex]v_1[/tex] и [tex]v_2[/tex], които не са свързани с път. Разглеждаш множествата [tex]V_i,\ i=1,2[/tex] от всички върхове, които са свързани с реброто [tex]v_i[/tex]. Според нашето допускане няма път между [tex]v_1[/tex] и [tex]v_2[/tex], следователно [tex]V_1\cap V_2=\emptyset[/tex].
Обаче двете множества имат мощности [tex]|V_i|\geq\frac{n-1}{2}[/tex] и след като имат празно сечение, то тяхното обединение има мощност [tex]|V_1\cup V_2|\geq \frac{n-1}{2}+\frac{n-1}{2}\geq n-1[/tex]. Обаче всички върхове са n, т.е. имаме максимум n-2 върха в [tex]V_1\cup V_2[/tex](след като изключим v_1 и v_2). Това е противоречие, което се дължи на допускането, че графът не е свързан. Следователно той е свързан.

[martin123456]

[asdf]

Мерси