Aristas de K₄.
Cada par forma una arista.
K₄ es el grafo simple completo de cuatro vértices: cada par distinto forma una arista.
Elegir sus extremos sin orden da C(4,2).
C(4,2)=4·3/2=6 aristas; la suma de grados4·3=12 también da6 al dividir por2.
Aristas de un árbol con 15 vértices.
n−1.
Un árbol finito es conexo y acíclico, por lo que tiene n−1 aristas.
Suma de grados de un grafo con siete aristas.
Cuenta cada arista dos veces.
Una arista no dirigida tiene dos extremos.
Al sumar los grados contamos cada una de las siete aristas dos veces.
Prueba que un árbol tiene camino único entre cada par.
Dos caminos distintos producirían un ciclo.
La conexión del árbol asegura al menos un camino entre cada par de vértices.
Si existieran dos diferentes, seguimos ambos desde su separación hasta su primer reencuentro.
Los tramos así obtenidos forman un ciclo, contradiciendo la ausencia de ciclos.
Por tanto el camino existe y es único.
Prueba que el número de vértices de grado impar es par.
Reduce la suma de grados módulo dos.
La suma de grados es2|E| y, por tanto, par.
Los grados pares contribuyen cero a la suma módulo2; cada grado impar contribuye uno.
El número de contribuciones impares debe ser par para que la suma sea par.
Así el número de vértices de grado impar es par, incluso si hay varios componentes.