Es

Question

Deje $G$ ser un simple gráfico (que es, sin bordes paralelos y bucles). Quiero saber ¿cómo se puede ir sobre formalmente demostrando la siguiente (si es verdad):

$$ \sum_{\{v,w\}\in E(G)}d(v)+d(w) = \sum_{v \V(G)}d(v)^2 $$

Intuitivamente, me he convencido a mí mismo desde el lado derecho puede ser pensado de una suma donde cada plazo $d(v)$ se resume exactamente $d(v)$ a veces, y el LHS verifica esta así: cada una de las $d(v)$ 'aparece' en uno de los sumandos si y sólo si existe una arista $e \in G$ que contiene $v$. Como esto sucede exactamente $|\{e \in G : v \in e\}|= d(v)$ tiempos, cada uno suma los mismos términos ocurring la misma cantidad de veces. ¿Cómo puedo decir esto con un poco más de rigor?

Answer 1

Tienes la idea correcta. Definir el conjunto de $\, F := {(v,e) \in V(G)\times E(G) : v \in e} \,$ de pares ordenados de todos los vértices y todas las aristas que contiene ese vértice. Considerar el % de la suma $\, \sum_{(v,e)\in F} d(v). \,$particiones naturalmente de dos maneras. Una forma es por vértices y el otro por los bordes. En el primer caso, aparece de cada vértice $\, v \,$ $\, d(v) \,$ veces y por lo tanto la suma es $\, d(v)^2. \,$ en el segundo caso, cada borde $\, {v,w} \,$ tiene dos vértices y aparece dos veces, una vez $\, v \,$ y $\, w, \,$ y, por tanto, la suma de $\, d(v)+d(w). \,$