Bonjour,
j'essaie de démontrer que la somme des carrés des degrés des sommets d'un graphe est égale à la somme des degrés des 2 sommets de chaque arête, soit pour G=(S,A) un graphe simple d'ordre n à m arêtes :
(x,y)
A (d(x)+d(y)) =
x
S d2(x)
Ce que je ne comprends pas, c'est pourquoi on a obligatoirement d(x)+d(y) =< n.
Est-ce à dire que la définition d'un graphe simple implique qu'il ne contienne pas de triangle?
Merci par avance pour vos éclaircissements.
Bonjour,
Je suis très fatigué, mais non, la définition d'un graphe n'est pas "contrainte". L'inégalité m'étonne aussi.
(j'aurais dit 2(n-1)).
Je vois...enfin je crois. En fait ça serait plutôt d(xy) non ? On "compresse" l'arrête xy, puis on estime le degré.
Dans ce cas, il est inférieur à n-2.
Merci pour votre réaction.
En fait, je ne parviens pas à justifier l'égalité des 2 sommes dans un graphe simple (cas le plus général).
On fait la somme sur les arêtes et un sommet x apparaît autant de fois que son degré.
Comme sa contribution est d(x), on a donc le x
S d2(x) ?
Merci à nouveau
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :