Determinación del número de grafos simples no dirigidos.

Question

Un grafo simple no dirigido no tiene bucles propios ni aristas paralelas.

Determinar el número de grafos simples no dirigidos $G = (V, E)$ con $V = {1, . . . , n}$

Además, ¿cómo puedo encontrar el número de grafos simples con vértices de grado 1?

¿Alguien conoce un método tradicional para resolver esto? Por favor, ayuda.

Answer 1

Asumiendo que tienes $N$ vértices y $M$ bordes, entonces como tienes $N$ vértices totales, lo que significa que tienes $$\sum_{k=1}^{N-1} k = \frac{N(N-1)}{2} = P$$ posibles bordes. Ahora, de esas $P$ , elija el $M$ que están presentes, es decir $P \choose M$ :).