Proof
(related to Corollary: Even Number of Vertices with an Odd Degree in Finite Digraphs)
- Let \(D=(V,E,\alpha,\omega)\) be a finite digraph and let \(O\subseteq V\) be the subset of all vertices with odd degree.
- Then it follows from the handshaking lemma that \[2|E|=\sum_{v\in V}d_D^+(v)+\sum_{v\in V}d_D^-(v)=\underbrace{\sum_{v\in V}d_D(v)}_{\text{even}}.\]
- On the other hand, we have \[\sum_{v\in V}d_D(v)= \underbrace{\sum_{v\in V\setminus O}d_D(v)}_{\text{even}}+\underbrace{\sum_{v\in O}(d_D(v)-1)}_{\text{even}}+|O|.\]
- Thus, \(|O|\) must be even, since it is a difference of even numbers.
∎
Thank you to the contributors under CC BY-SA 4.0! 
- Github:
-
References
Bibliography
- Krumke S. O., Noltemeier H.: "Graphentheoretische Konzepte und Algorithmen", Teubner, 2005, 1st Edition
