Demostrando que $\sum \deg(v) = 2m$ para cualquier gráfico $G$

Question

Aquí está mi prueba, por favor corrígeme si me equivoco, trato de ser formal.

Prueba por inducción:

Sea $\sum \deg(v)=2m$ supuesto... cuando #de nodos es $n=0$ . así que aquí la ecuación es $\sum \deg(v)=2(0)=0$ [verdadero para 0] .... (1)

ahora si añadimos un nuevo nodo $w$ y conectarlo al nodo v, entonces esperamos que sólo el grado de $v$ y $w$ aumentará en $1+1 =2$ y

así que haciendo eso como lo siguiente: $\sum \deg(v)=2 + 2m = 2(m+1)$ , entonces nuestra suposición es cierta porque cuando añadimos 1 arista, el número total de aristas aumenta en $2(m+1)$ .

¿Es una prueba correcta y formal?

Answer 1

Tal como está escrito, esto sólo demuestra la proposición para grafos conexos sin ciclos. En tu paso inductivo añades un nuevo vértice y arista a un grafo existente. Esto restringe los tipos generales de grafos. Sin embargo, es correcto en su mayor parte, así es como yo lo modificaría.

En primer lugar, en lugar de inducir sobre el número de vértices de un grafo $n$ Utiliza el número de aristas $m$ . Ahora tu paso inductivo puede ser así: Supongamos que tenemos un gráfico $G$ con $m$ bordes. Elimina una arista al azar. El gráfico resultante $G'$ tiene $m-1$ aristas, y por inducción, sabemos que la proposición es válida para ese grafo. Por lo tanto, $\sum \deg(v) = 2(m-1)$ para el subgrafo $G'$ . $G$ es sólo el gráfico $G'$ con un borde más. Como esta arista está conectada a dos vértices en $G$ el grado de cada uno de esos vértices ha aumentado en uno. Así que $\sum \deg(v) = 2(m-1) + 2 = 2m$ para el gráfico $G$ .

Así se obtendría una prueba formal completa.

Actualización

Para el caso base tendrás que demostrar la proposición para todos los grafos con $0$ bordes. A saber, los grafos formados por $0$ o más vértices y ninguna arista.