Hola
5. Considere un grafo sin loops con \( n\geq 2 \) vértices. Muestre que dos de ellos tienen la misma valencia.
Si todos los vértices tuviesen distinta valencia, dado que la mínima posible es \( 0 \) y la máxima es \( n-1 \) tendríamos que valencias son exactamente \( \{0,1,2,\ldots,n-1\} \). Pero el de valencia \( n-1 \) estaría conectado con los \( n-1 \) restantes, pero eso contradice que el primero tenga valencia cero.
6. Pruebe que todo grado sin loops con \( n \) vértices y más de \( \displaystyle\binom{n-1}{2} \) aristas es conexo.
Si no fuese conexo al menos se descompone en al menos dos subgrafos disjuntos con \( k \) y \( n-k \) vértices. Supongamos sin pérdida de generalidad \( k\leq n-k \).
Si \( k=1 \) el grafo de \( 1 \) vértice no tiene aristas y el otro a lo sumo tiene \( \displaystyle\binom{n-1}{2} \) aristas. No cumple la hipótesis.
Si \( k>2 \) cada subgrafo tiene a lo sumo \( \displaystyle\binom{k}{2} \) y \( \displaystyle\binom{n-k}{2} \) aristas.
Pero veamos que:
\( \displaystyle\binom{k}{2}+\displaystyle\binom{n-k}{2}\leq \displaystyle\binom{n-1}{2} \)
Equivale a comprobar que:
\( (n-1)(n-2)\geq k(k-1)+(n-k)(n-k-1) \)
Pero:
\( (n-1)(n-2)-k(k-1)+(n-k)(n-k-1)=2(k-1)(n-k-1)\geq 0 \)
Saludos.
