A soma dos graus de entrada $\sum_{v\in V} id(v)$e graus de saída $\sum_{v\in V} od(v)$são sempre iguais?

Question

Estou trabalhando no Problema #24 da seção 11.3 de Matemática Discreta e Combinatória de Ralph P. Grimaldi, uma Introdução Aplicada, quinta edição.

Pergunta:

Deixar$G=(V,E)$seja um grafo direcionado, onde$|V|=n$e$|E|=e$. Quais são os valores para$\sum_{v\in V} id(v)$e$\sum_{v\in V} od(v)$?

$id(v)$e$od(v)$são os graus de entrada e de saída.

Os graus de entrada e saída são mencionados de passagem no final da seção 11.3, de modo que é deixado por conta própria para responder a essa pergunta.

Tentei deduzir os fatos necessários sobre$\sum_{v\in V} id(v)$e$\sum_{v\in V} od(v)$e gostaria de saber se minha lógica está correta:

Dado um número finito de vértices$n$para cada aresta 'direcionada' que você adiciona, você está adicionando$1$para$\sum_{v\in V} id(v)$e$\sum_{v\in V} od(v)$respectivamente, e eles devem ser sempre iguais?

Se sim, então$\sum_{v\in V} id(v)=\sum_{v\in V} od(v)=e?$

Answer 1

Para tornar sua ideia rigorosa, você precisa usar a indução. Deixar$Q(k)$seja a afirmação de que todo grafo direcionado com exatamente$k$arestas satisfaz a afirmação desejada. Em seguida, use indução em$Q$. Ao fazer isso, tome cuidado para não fazer nada como "Se$Q(k)$é verdade, então vamos$G$seja qualquer grafo direcionado com$k$arestas e adicione uma aresta..."! Leia esta explicação de indução para ter certeza de que você fez a indução corretamente.