# TDA | Practica 3 ejercicio 2 ## Consigna - Demostrar, usando reducción al absurdo que: - **todo grafo no trivial (o sea que por lo menos tiene dos vertices) tiene al menos dos vertices del mismo grado**. ## Resolución ### Demostración: - Sea $G(V,E)$ un grafo no trivial con $|V| = n$ vértices. Cada $v \in V$ tiene un grado $d(v)$, que varía entre $[0, n-1]$. - Supongamos, para llegar a una contradicción, que todos los grados de los vértices son diferentes. Entonces, los grados posibles de los $n$ vértices estarían en {$0, \dots, n-1$}. - Sin embargo, si un vértice tiene grado cero, significaría que está aislado, y si otro vértice tiene grado $n-1$, significa que está conectado a todos los demás vértices. - Esto crea una situación imposible bajo nuestra suposición inicial, ya que no podríamos tener un conjunto de grados únicos para todos los vértices sin violar esta condición. - Por lo tanto, nuestra suposición inicial de que todos los vértices tienen grados distintos lleva a una contradicción, demostrando que debe haber al menos dos vértices en cualquier grafo no trivial que tengan el mismo grado. $\square$