Es posible que esto sea sencillo, pero me gustaría comprobar mi razonamiento porque parece "demasiado sencillo".
Consideremos un grafo no dirigido de $N$ nodos.
Lo configuramos de manera que cada nodo esté conectado a un número fijo de otros nodos, es decir, que cada nodo tenga el mismo grado, $k$ .
Me gustaría saber cuántas aristas hay en el gráfico. Sería menos de $kN$ porque una de las aristas del nodo A dice $\overline{AB}$ también contaría como una de las aristas de B.
La forma en que abordé el problema fue considerar la matriz de adyacencia $A$ . Como el gráfico no está ponderado, cada fila de la matriz tendría $k$ en ella. Así que la suma de todos los elementos en $A$ sería $kN$ .
Como el grafo es no dirigido, la matriz es simétrica y toda la información relevante sobre las aristas está en la diagonal superior de $A$ .
El gráfico no contiene bucles propios, por lo que $\text{tr}(A) = 0$ .
Por lo tanto, el número total de aristas únicas debe ser $1/2$ la suma de toda la matriz $A$ o:
$$\text{number of edges} = \frac{kN}{2} $$
¿Le parece bien? O me falta algo en mi lógica. Soy nuevo en la teoría de grafos. No he visto este problema abordado en cualquier lugar sólo, lo que me hace pensar que es demasiado complicado o trivial.
Merci
