Neka netko pogleda ovo, malo mi je sumnjivo: Reformulirat ćemo zadatak na sljedeći način: Neka je
graf sa čvorovima
, te neka su
i
povezani crvenim bridom akko je
, inače su povezani plavom . Tvrdnja zadatka je da ne možemo odabrati
-člani podskup čvorova tako da nijedna 2 čvora nisu povezana.
Ako pogledamo čvor
za bilo koji
, razlikujemo 3 slučaja:
1. ![x \leq k](/media/m/6/6/f/66f961fb7654082f3580317859cede73.png)
u tom slučaju su svi čvorovi sa kojima je spojen
do
, odnosno ima ih ![k-1](/media/m/e/2/5/e2582f1a41d7cbbc089069312ee7488a.png)
2. ![k<x \leq 2k](/media/m/b/1/2/b129187cfc9ddf61e98fac1b30f9728f.png)
ako
zapišemo u obliku
,
je povezan sa
do
, te sa
do
, odnosno ukupno ![(z-1)+(k-z)=k-1](/media/m/b/2/7/b2769ba00b10d86d31d4ac964b05c945.png)
3. ![x>2k](/media/m/a/7/e/a7e9db62cd8120c7d209c23325b0b225.png)
Neka je opet
sada je
povezan sa
do
, odnosno
njih
To znači da svaki čvor ima stupanj crvenih
. Također, za svaki čvor je jednistveno određen njegov skup čvorova s kojim je povezan bridom fiksne boje
pretpostavimo da je moguće odabrati takvih
čvorova. Broj svih bridova je
, a to možemo podijeliti na 3 klase:
1. klasa obuhvaća plave bridove među odabranih
čvorova, njih ima ![\frac{(k+2)(k+1)}{2}](/media/m/3/3/f/33f31e886420db6ebc51e17b6c95e6b6.png)
2. klasa obuhvaća sve crvene bridove, njih ima ![\frac{3k(k-1)}{2}](/media/m/f/e/4/fe4212fa4f9e9c0f3d1a3942088c6640.png)
3. klasa sadržava sve ostale plave, kojih ima ![\frac {(2k-2)(2k)}{2}](/media/m/3/c/a/3ca585b2242ab8f2c30849a27d7921f8.png)
Zbrajanjem se dobiva:
.
![9k^2-3k=k^2+3k+2+3k^2-3k+4k^2-4k](/media/m/d/c/a/dcaa029685c7ce9ef63917e731d4f9c9.png)
![k^2+k-2=0](/media/m/5/8/2/58247de78a1c54ea74af38d8a775ad3f.png)
![(k+2)(k-1)=0](/media/m/9/f/7/9f769ea48306d319a5a15c202131e801.png)
Pozitivno je rješenje
, ali kako je to protivno uvjetu zadatka, dobili smo kontradikciju, odnosno traženi odabir nije moguć, te smo gotovi
Neka netko pogleda ovo, malo mi je sumnjivo:
Reformulirat ćemo zadatak na sljedeći način:
Neka je $\mathbb{G}$ graf sa čvorovima $a_1, a_2, \dots a_{3k}$, te neka su $a_i$ i $a_j$ povezani crvenim bridom akko je $k<|i-j|<2k$, inače su povezani plavom . Tvrdnja zadatka je da ne možemo odabrati $(k+2)$-člani podskup čvorova tako da nijedna 2 čvora nisu povezana.\\
Ako pogledamo čvor $a_x$ za bilo koji $x$, razlikujemo 3 slučaja:\\
1. $x \leq k$\\
u tom slučaju su svi čvorovi sa kojima je spojen $a_{x+k+1}$ do $a_{x+2k-1}$, odnosno ima ih $k-1$
2. $k<x \leq 2k$\\
ako $x$ zapišemo u obliku $k+z$, $a_x$ je povezan sa $a_1$ do $a_{z-1}$, te sa $a_{2k+z+1}$ do $a_{3k}$, odnosno ukupno $(z-1)+(k-z)=k-1$
3. $x>2k$\\
Neka je opet $x=2k+z$
sada je $a_x$ povezan sa $a_{z+1}$ do $a_{k+z-1}$, odnosno $k-1$ njih
To znači da svaki čvor ima stupanj crvenih $k-1$. Također, za svaki čvor je jednistveno određen njegov skup čvorova s kojim je povezan bridom fiksne boje
pretpostavimo da je moguće odabrati takvih $k+2$ čvorova.
Broj svih bridova je $\frac{3k(3k-1)}{2}$, a to možemo podijeliti na 3 klase:\\
1. klasa obuhvaća plave bridove među odabranih $k+2$ čvorova, njih ima $\frac{(k+2)(k+1)}{2}$\\
2. klasa obuhvaća sve crvene bridove, njih ima $\frac{3k(k-1)}{2}$\\
3. klasa sadržava sve ostale plave, kojih ima $\frac {(2k-2)(2k)}{2}$\\
Zbrajanjem se dobiva:\\
$\frac{3k(3k-1)}{2} = \frac{(k+2)(k+1)}{2}+ \frac{3k(k-1)}{2}+\frac {(2k-2)(2k)}{2}$.\\
$9k^2-3k=k^2+3k+2+3k^2-3k+4k^2-4k$\\
$k^2+k-2=0$\\
$(k+2)(k-1)=0$\\
Pozitivno je rješenje $k=1$, ali kako je to protivno uvjetu zadatka, dobili smo kontradikciju, odnosno traženi odabir nije moguć, te smo gotovi