Demostrar que si G es un dígrafo cuyo grafo subyacente es regular, entonces se cumple la siguiente fórmula.

Question

Demostrar que si $G$ es un dígrafo cuyo gráfico subyacente es regular, entonces $$\sum_{i=1}^n\operatorname{outdeg}^2(v_i)=\sum_{i=1}^n\operatorname{indeg}^2(v_i)\;.$$

Este es un problema de asignación, así que por favor no me den directamente la solución. No tengo casi ninguna idea sobre este problema, lo que sé es:

1. El dilema del apretón de manos: $$m=\sum_{i=1}^n\operatorname{outdeg}(v_i)=\sum_{i=1}^n\operatorname{indeg}(v_i)$$

2. Qué es un gráfico subyacente.

3. Ya que es $k$ -regular, lo que significa que para cada vértice $v_i$ en $G$ , $\operatorname{outdeg}(v_i)+\operatorname{indeg}(v_i)= k$ .

Se agradecen los consejos. Gracias.

Answer 1

SUGERENCIA:

$$\sum_{i=1}^n\operatorname{outdeg}^2(v_i)=\sum_{i=1}^n\operatorname{indeg}^2(v_i)$$

si y sólo si

$$\begin{align*} 0&=\sum_{i=1}^n\operatorname{outdeg}^2(v_i)-\sum_{i=1}^n\operatorname{indeg}^2(v_i)\\ &=\sum_{i=1}^n\left(\operatorname{outdeg}^2(v_i)-\operatorname{indeg}^2(v_i)\right)\\ &=\sum_{i=1}^n\big(\operatorname{outdeg}(v_i)-\operatorname{indeg}(v_i)\big)\big(\operatorname{outdeg}(v_i)+\operatorname{indeg}(v_i)\big)\\ &=k\sum_{i=1}^n\big(\operatorname{outdeg}(v_i)-\operatorname{indeg}(v_i)\big)\;, \end{align*}$$

donde el gráfico subyacente es $k$ -regular.