MATEMANIJA

Kao prvo izvinjavam se ako postavljam temu koja već postoji, ili nije na odgovarajućem 'mestu'. Naime zadatak je iz predmeta diskretna matematika, ali na nekim smerovima se ovaj predmet zove i 'Teorija skupova i matematička logika'. Da ne dužim više zadatak glasi ovako:

Odrediti sve parove prirodnih brojeva [inlmath](n,k)[/inlmath] za koje važi: Postoji [inlmath]k[/inlmath]-regularan graf sa [inlmath]n[/inlmath] čvorova.

E sad, pod [inlmath]k[/inlmath]-regularnim grafom smatra se graf čiji čvorovi imaju jednake stepene, odnosno graf kod kog svaki čvor ima jedan broj grana. Evo i nekih primera [inlmath]k[/inlmath]-regularnih grafova:


Ali kako se radi ovaj zadatak, stvarno ne znam pa bi mi dobrodošla pomoć
Hvala unapred!

Postoji predmet i 'Teorija grafova'

Da li ti je poznata Erdos Gallai teorema za niz stepena čvorova grafa, koja otprilike kaže: Niz stepena nekog grafa sa [inlmath]n[/inlmath] čvorova je [inlmath]d_1\ge\cdots\ge d_n\iff\sum\limits_{i=1}^nd_i[/inlmath] je parna i [inlmath]\sum\limits_{i=1}^pd_i\le p(p-1)+\sum\limits_{i=p+1}^n\min\{d_i,p\},\;p\in\{1,2,\ldots,n\}[/inlmath], za svako [inlmath]p[/inlmath], tako da [inlmath]1\le p\le n[/inlmath] ?

Dokažimo da je tvrdnja zadatka tačna za [inlmath]k[/inlmath] ili [inlmath]n[/inlmath] parno
Za [inlmath]d_1\ge\cdots\ge d_n=k[/inlmath] se lako ispituje
Za [inlmath]k=n-1[/inlmath] trivijalno znamo da postoji regularan graf [inlmath]K_n[/inlmath]
Pretpostavimo da je [inlmath]k<n-1[/inlmath]. Za [inlmath]1\le p\le k[/inlmath] je [inlmath]p(p-1)+p(k-p)+(n-k)k-pk=nk-k^2-p\ge nk-k^2-k=k(n-k-1)>0[/inlmath]
Za [inlmath]p>k[/inlmath] imamo [inlmath]p(p-1)+k(n-p)-pk=p^2-p(2k+1)+nk=\left(p-\frac{2k+1}{2}\right)^2+nk-\left(\frac{2k+1}{2}\right)^2[/inlmath]
Za [inlmath]k<n-1[/inlmath] je
[dispmath]4nk>4k^2+4k[/dispmath][dispmath]4nk\ge4k^2+4k+1[/dispmath][dispmath]4nk\ge(2k+1)^2[/dispmath] Te imamo da je [inlmath]p(p-1)+k(n-p)-pk\ge0[/inlmath]
Ako je [inlmath]kn[/inlmath] parno, tvrdnja zadatka je tačna

mala_mu je napisao:Pretpostavimo da je [inlmath]k<n-1[/inlmath]. Za [inlmath]1\le p\le k[/inlmath] je [inlmath]p(p-1)+p(k-p)+(n-k)k-pk=nk-k^2-p\ge nk-k^2-k=k(n-k-1)>0[/inlmath]

Zapravo, nejednakost za ovaj slučaj bi trebalo da glasi (nakon uvrštavanja [inlmath]k[/inlmath] umesto [inlmath]d_i[/inlmath] i uslova da je [inlmath]\min\{k,p\}=p)[/inlmath]:
[dispmath]\underbrace{\sum\limits_{i=1}^pk}_{pk}\le p(p-1)+\sum_{i=p+1}^n\underbrace{\min\{k,p\}}_p\\
pk\le p(p-1)+\underbrace{\sum_{i=p+1}^np}_{(n-p)p}\\
pk\le p(p-1)+(n-p)p[/dispmath] Zatim podelimo obe strane sa [inlmath]p[/inlmath] (što smemo da učinimo, zbog uslova da je [inlmath]p\ge1[/inlmath], što znači da [inlmath]p[/inlmath] ne može biti ni nula ni negativno,
[dispmath]k\le\cancel p-1+n-\cancel p\\
k\le n-1[/dispmath] čime je dokazano da je polazna nejednakost ispunjena, jer je po pretpostavci [inlmath]k<n-1[/inlmath].

---

Inače, uslov da [inlmath]\sum\limits_{i=1}^nd_i[/inlmath] kod svih grafova (ne samo regularnih) mora biti parno prilično je očigledan. Pošto svaka grana koja povezuje dva čvora povećava stepen oba ta čvora za jedan, to povećava sumu svih stepena čvorova za dva (isti slučaj i s granama koje predstavljaju petlje, one povećavaju stepen tog jednog čvora za dva), odatle sledi da je suma stepena svih čvorova jednaka dvostrukom broju grana u grafu. A pošto je broj grana u grafu prirodan broj, sledi da suma stepena svih čvorova, kao proizvod prirodnog broja i broja dva, mora biti paran broj.