La suma de los grados $\sum_{v\in V} id(v)$y fuera de grados $\sum_{v\in V} od(v)$son siempre iguales?

Question

Estoy trabajando en el problema #24 de la sección 11.3 de Matemáticas discretas y combinatorias de Ralph P. Grimaldi, una introducción aplicada, quinta edición.

Pregunta:

Dejar$G=(V,E)$sea ​​un grafo dirigido, donde$|V|=n$y$|E|=e$. ¿Cuáles son los valores para$\sum_{v\in V} id(v)$y$\sum_{v\in V} od(v)$?

$id(v)$y$od(v)$son los grados de entrada y los grados de salida.

Los grados de entrada y salida se mencionan de pasada al final de la sección 11.3, por lo que uno se queda solo para responder esta pregunta.

Traté de deducir los hechos necesarios sobre$\sum_{v\in V} id(v)$y$\sum_{v\in V} od(v)$y me gustaría saber si mi lógica es correcta:

Dado un número finito de vértices$n$por cada borde 'dirigido' que agrega, está agregando$1$para$\sum_{v\in V} id(v)$y$\sum_{v\in V} od(v)$respectivamente, y deben ser siempre iguales?

Si es así, entonces$\sum_{v\in V} id(v)=\sum_{v\in V} od(v)=e?$

Answer 1

Para hacer que su idea sea rigurosa, necesita usar la inducción. Dejar$Q(k)$sea ​​el enunciado de que todo grafo dirigido con exactamente$k$bordes satisface la demanda deseada. Luego usa la inducción en$Q$. Al hacerlo, tenga cuidado de no hacer algo como "Si$Q(k)$es cierto, entonces deja$G$Sea cualquier gráfico dirigido con$k$aristas y agregue una arista..."! Lea esta explicación de inducción para asegurarse de hacer la inducción correctamente.