Сумма в градусах $\sum_{v\in V} id(v)$ и вне дипломов $\sum_{v\in V} od(v)$ всегда равны?

Question

Я работаю над проблемой № 24 раздела 11.3 книги Ральфа П. Гримальди «Дискретная и комбинаторная математика, прикладное введение», пятое издание.

Вопрос:

Позволять $G=(V,E)$ ориентированный граф, где $|V|=n$ а также $|E|=e$. Какие ценности для$\sum_{v\in V} id(v)$ а также $\sum_{v\in V} od(v)$?

$id(v)$ а также $od(v)$ - внутренние и внешние степени.

Входящие и исходящие степени упоминаются попутно в конце раздела 11.3, поэтому каждый может сам ответить на этот вопрос.

Я пытался вывести необходимые факты о $\sum_{v\in V} id(v)$ а также $\sum_{v\in V} od(v)$ и я хотел бы знать, верна ли моя логика:

Учитывая конечное число вершин $n$ для каждого добавляемого «направленного» края вы добавляете $1$ к $\sum_{v\in V} id(v)$ а также $\sum_{v\in V} od(v)$ соответственно и они всегда должны быть равны?

Если да, то $\sum_{v\in V} id(v)=\sum_{v\in V} od(v)=e?$

Answer 1

Чтобы ваша идея была точной, вам нужно использовать индукцию. Позволять$Q(k)$ - утверждение, что любой ориентированный граф с точно $k$ребра удовлетворяет желаемому требованию. Затем используйте индукцию по$Q$. При этом будьте осторожны, не делайте ничего вроде «Если$Q(k)$ верно, тогда пусть $G$ любой ориентированный граф с $k$ребер и добавить ребро ... "! Прочтите это объяснение индукции, чтобы убедиться, что вы делаете индукцию правильно.