Die Summe der In-Grade $\sum_{v\in V} id(v)$und Aus-Grade $\sum_{v\in V} od(v)$sind immer gleich?

Question

Ich arbeite an Problem Nr. 24 in Abschnitt 11.3 von Ralph P. Grimaldis Discrete and Combinatorial Mathematics, an Applied Introduction, fünfte Auflage.

Frage:

Lassen$G=(V,E)$sei ein gerichteter Graph, wobei$|V|=n$und$|E|=e$. Wofür sind die Werte$\sum_{v\in V} id(v)$und$\sum_{v\in V} od(v)$?

$id(v)$und$od(v)$sind die In-Grade und Out-Grade.

In- und Out-Grade werden am Ende von Abschnitt 11.3 am Rande erwähnt, so dass man sich selbst überlassen bleibt, diese Frage zu beantworten.

Ich habe versucht, die notwendigen Fakten über abzuleiten$\sum_{v\in V} id(v)$und$\sum_{v\in V} od(v)$und ich würde gerne wissen, ob meine Logik richtig ist:

Gegeben sei eine endliche Anzahl von Knoten$n$für jede "gerichtete" Kante, die Sie hinzufügen, fügen Sie hinzu$1$zu$\sum_{v\in V} id(v)$und$\sum_{v\in V} od(v)$jeweils, und sie müssen immer gleich sein?

Wenn ja, dann$\sum_{v\in V} id(v)=\sum_{v\in V} od(v)=e?$

Answer 1

Um Ihre Idee streng zu machen, müssen Sie Induktion verwenden. Lassen$Q(k)$sei die Aussage, dass jeder gerichtete Graph mit genau$k$Kanten erfüllt den gewünschten Anspruch. Dann Induktion einschalten$Q$. Achten Sie dabei darauf, dass Sie nichts wie „If$Q(k)$wahr ist, dann lassen Sie$G$sei irgendein gerichteter Graph mit$k$Kanten und füge eine Kante hinzu..."! Lies diese Erklärung der Induktion , um sicherzustellen, dass du die Induktion richtig durchführst.