Suma stopni w stopniach $\sum_{v\in V} id(v)$ i poza stopniami $\sum_{v\in V} od(v)$ są zawsze równe?

Question

Pracuję nad Problemem nr 24 w sekcji 11.3 książki Discrete and Combinatorial Mathematics Ralpha P. Grimaldiego, wprowadzenie stosowane, wydanie piąte.

Pytanie:

Pozwolić $G=(V,E)$ być grafem skierowanym, gdzie $|V|=n$ i $|E|=e$. Jakie są wartości?$\sum_{v\in V} id(v)$ i $\sum_{v\in V} od(v)$?

$id(v)$ i $od(v)$ są stopnie wejściowe i zewnętrzne.

Stopnie wejściowe i wyjściowe są wymienione mimochodem na końcu sekcji 11.3, więc odpowiedź na to pytanie jest pozostawiona samemu sobie.

Próbowałem wydedukować niezbędne fakty na temat $\sum_{v\in V} id(v)$ i $\sum_{v\in V} od(v)$ i chciałbym wiedzieć, czy moja logika jest poprawna:

Biorąc pod uwagę skończoną liczbę wierzchołków $n$ za każdą „kierowaną” krawędź, którą dodajesz, dodajesz $1$ do $\sum_{v\in V} id(v)$ i $\sum_{v\in V} od(v)$ odpowiednio i muszą być zawsze równe?

Jeśli tak, to $\sum_{v\in V} id(v)=\sum_{v\in V} od(v)=e?$

Answer 1

Aby Twój pomysł był rygorystyczny, musisz użyć indukcji. Pozwolić$Q(k)$ być stwierdzeniem, że każdy skierowany graf z dokładnie $k$krawędzie spełniają pożądane wymagania. Następnie użyj indukcji na$Q$. Robiąc to, uważaj, aby nie zrobić czegoś takiego jak „Jeśli$Q(k)$ to prawda, więc pozwól $G$ być dowolnym grafem skierowanym z $k$krawędzie i dodaj krawędź..."! Przeczytaj to wyjaśnienie indukcji, aby upewnić się, że indukcja przebiega prawidłowo.