Hola
Al momento estoy tratando de entender las demostración por doble conteo, y que mejor que un ejemplo. La siguiente proposición se conoce como el lema del apretón de manos:
Sea \( G \) un grafo, \( V \) el conjunto de todos sus vértices y \( E \) el conjunto de todos sus ejes todas sus aristas. Entonces
\( \displaystyle\sum_{v\in V} d(v)=2|E| \),
donde \( d(v) \) representa la valencia del vértice \( v \in V \)
He escuchado que esta proposición tiene varias demostraciones y yo quisiera ver aquí podría dar una demostración rigurosa por doble conteo de este resultado. Esto me ayudaría mucho a entender el método de demostración lo cual es principalmente lo que necesito. Muchas gracias a todos por su atención.
Desde un punto de vista intuitivo: cada vértice \( v \) está contenido en \( d(v) \) aristas, además cada arista contiene exactamente dos vértices. Por tanto si sumamos las valencias obtenemos el doble del número de aristas.
Si lo quieres formalizar al máximo. Ten primero en cuenta este resultado:
(A) Dada un aplicación sobreyecitva \( f:A\to B \) entre conjuntos finitos \( card(A)=\displaystyle\sum_{b\in B} card(f^{-1}(b)) \)
Spoiler
La demostración de esto es inmediata teniendo en cuenta que los conjuntos de la familia \( \{f^{-1}(b)\}_{b\in B} \) son disjuntos por definición de imagen recíproca y su unión es \( A \) por ser la aplicación sobreyectiva.
Sea \( V' \) el conjunto de vértices de valencia mayor que cero.
Ahora considera el conjunto \( A=\{(v,e)\in V'\times E|v\in E\} \) y las aplicaciones:
\( g_1:A\to V',\qquad g_1(v,e)=v \)
\( g_2:A\to E,\qquad g_2(v,e)=e \)
Es inemdiato que:
1) Ambas son sobreyectivas, ya que todo vértice de \( V' \) pertenece a alguna arista y toda arista tiene algún vértices.
2) Para todo \( v\in V', \) se tiene que \( g_1^{-1}(v)=\{(v,e)|v\in e\} \) (es decir el conjunto de aristas que contienen a \( v \)) y por definición \( card(g_1^{-1}(v))d(v) \).
3) Para todo \( e\in E \) se tiene que \( g_2^{-1}(e)=\{(v,e)|v\in e\}=\{(v_i,e),(v_f,e)\} \) donde \( \{v_i,v_f\} \) son los dos vértices que forman la arista \( e \). Por tanto \( card(g_2^{-1}(e))=2 \).
4) Aplicando el resultado (A) a ambas aplicaciones se obtiene:
\( card(A)=\displaystyle\sum_{v\in V'}card(g_1^{-1}(v))=\displaystyle\sum_{v\in V'}d(v)=\displaystyle\sum_{v\in V}d(v) \) ya que los vértices fuera de \( V' \) tienen valencia cero.
\( card(A)=\displaystyle\sum_{e\in E}card(g_2^{-1}(e))=\displaystyle\sum_{e\in E}2=2\displaystyle\sum_{e\in E}1=2card(E) \)
Igualando ambas cosas tienes el resultado.
Saludos.
