Graphe, degré et voisins

[invite8650b788]

Bonjour,

Auriez-vous la gentillesse de m'aiguiller pour finir de résoudre cet exercice.
Avec G={S,A}, d'ordre n à m arêtes.
On définit V(x) comme l'ensemble des voisins de x dans G.
On a donc d(x) = |V(x)| soit (card v(x)).

J'ai démontré que le nombre de triangles dans G est égal à 1/3 * SOMME_{(x,y)€ A} |V(x)V(y)|.

Je ne parviens pas à avancer pour montrer que :

1) |V(x) + V(y)| >= d(x) + d(y) - n ,
2) Le nombre de triangles dans G est sup ou égal à (4m/3n) * (m - (n2/4)).

Merci par avance de vos indications.

PS : ai aussi démontré que SOMME_{(x,y) € A} (d(x) + d(y)) = SOMME_{x € S} d²(x),
et SOMME_{x € S} d²(x) >= 4m²/n.
-----

[invite8650b788]

est-ce que le fait que d(x) =< n-1 est une piste?

[invite8650b788]

Quelqu'un peut-il me dépanner?

[invited5b2473a]

1 ) Tu peux faire un schéma pour t'aider.
2) Tu te sers de 1) et par récurrence.

[A voir en vidéo sur Futura]

[invite8650b788]

Merci de votre aide. Ai trouvé à l'aide du crible.
Cordialement.