O problema de teoria grafurilor

[•MciprianM]

Textul(asa cum l-am primit) e urmatorul:

"3. a) Prove that in a graph with n vertices (n ≥ 3) which does not contain triangles
(i.e. does not contain cycles of length 3) the sum of degrees of every two adjacent
vertices is at most 3.
b) In a contest there are 15 participants and each of them must play a game with each
other participant. During the contest one remark that, no matter how one chooses
three persons, there exist two which haven't play yet together. Show that there exist
at least one person which has already played at most 8 games.
c) Which is the maximum number of edges of a graph with n vertices which does not
contain triangles? For which kind of graphs this maximum is attained?
d) Construct a connected graph with n vertices (n ≥ 5) which contains at least a
triangle, such that the sum of degrees of every two adjacent vertices is at most n."

Observatie. Punctul a) mi se pare gresit.
Observatie. In principal ma intereseaza punctul b).

Pentru punctul b) am incercat sa fac asa:
S=Sum_{{subgrup de trei noduri g}}1/2Sum_{{x nod in g}}degree(x);
S<=C³_n*2 (2* combinari de n luate cate trei)
De asemenea S=m*(n-2);(Fiecare muchie e luata in considerare de n-2 ori);
Si am obtinut m<=n*(n-1)/3; Pentru n=15=>m<=70;
Am presupus ca fiecare persoana a jucat cel putin 9 jocuri si am obtinut ca m>=68.
Ceea ce cred ca nu e bine. Cred ca problema e in afirmatia in italic de mai sus.

De asemenea daca stiti ceva carti cu genul asta de probleme va rog sa le postati. Multumesc.

[•wefgef]

a) In loc de 3 trebuie sa fie n. Rezolvarea este evidenta.
b) Te folosesti de punctul a). Reduci la absurd: consideri 2 noduri adiacente, suma gradelor este cel putin 16 > 15 - contradictie.
c) Cred ca e graful bipartit complet cu N/2 noduri intr-o parte.
d) Se gasesc multe exemple de mana.

[•MciprianM]

Mersi. Cred ca am inteles rezolvarea.