od dobry_den » 31. 5. 2009 21:32
Jinak k te sedmicce - ja myslim, ze by se na to mohlo jit sporem. Necht existuje A podmozina E(G) takova, ze |A| < n a G(V, E-A) je nesouvisly. Mejme takovou A nejmensi. Potom se graf rozdeli do dvou komponent souvislosti o (n-k) a (n+k) vrcholech. Potom celkovy soucet stupnu v (n-k) komponente by mel byt (n-k)*n - |A| = n^2 - nk - |A|. To ovsem neni mozne - uvazme graf K_(n-k), tedy uplny graf na (n-k) vrcholech. V nem je soucet stupnu (n-k)(n-k-1) = (n^2 - nk) - (n+k(n-k-1)) < (n^2 - nk) - |A|...
Kdyztak komentujte, je to takovy trochu divny...
Jinak k te sedmicce - ja myslim, ze by se na to mohlo jit sporem. Necht existuje A podmozina E(G) takova, ze |A| < n a G(V, E-A) je nesouvisly. Mejme takovou A nejmensi. Potom se graf rozdeli do dvou komponent souvislosti o (n-k) a (n+k) vrcholech. Potom celkovy soucet stupnu v (n-k) komponente by mel byt (n-k)*n - |A| = n^2 - nk - |A|. To ovsem neni mozne - uvazme graf K_(n-k), tedy uplny graf na (n-k) vrcholech. V nem je soucet stupnu (n-k)(n-k-1) = (n^2 - nk) - (n+k(n-k-1)) < (n^2 - nk) - |A|...
Kdyztak komentujte, je to takovy trochu divny...