I am starting to learn about graph theory and in the study of the graph theory proofs, I have inevitably come across the handshake lemma for undirected graphs which is a quite straight forward proof, be it as a direct proof or by induction.
Regarding the di-graphs however, all proofs I have come across so far, seem too simplistic direct proofs that leave the reader longing for a more rigorous detail.
They usually state:
Let $G=(V,E)$ be a di-graph, then
$\sum_{v\in V} \text{in-deg}(v) = |E| = \sum_{v\in V} \text{out-deg}(v)$
Proof: Each added edge increases both sums by one. $\blacksquare$
Can someone direct me towards a more detailed proof?
Best Answer
The proof idea can be explained by induction on the number of edges. If there are no edges in the graph then the proposition is obviously true. This is the base case of induction.
Now let $G$ be a digraph with at least $1$ edge. By induction, the proposition holds for $G-e$, where $e$ is any edge in $G$. Adding this edge back to $G-e$ is where we use "both sums increase by one" and we are done.