Examen Final - 61.07. Matemática Discreta - 17/07/2013

Cátedra: Todas
Día: 17/07/2013

Enunciado

Se tiene un grafo disconexo de componentes (subgrafos conexos) y vértices. La cantidad de aristas se maximiza cuando todas excepto una (k - 1) de las componentes del grafo son vértices aislados (si una de estas componentes tuviese dos vértices, uno de ellos se puede llevar a otra componente con más vértices y generaría más aristas entre estos últimos vértices). La última componente, claramente, sería un grafo K-regular.
Entonces se tienen vértices aislados y un grafo -regular. Ahora bien, para un grafo genérico k-regular la cantidad de aristas está determinada por

Y para el caso, se tiene que

A esta sumatoria le aplicamos Gauss para que finalmente nos quede expresada como

■