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
Sorry I'm late a black cat blocked my path so I had to take a different way then a dragon came down and blocked my path then I saw an old lady having trouble crossing the street so I helped her then a cat was stuck in a tree and the owners asked me to help then I got lost on the road of life