Grinberg-Introduction-Graph-Theory · Problem 4.10

Digraphs and multidigraphs

Mathematics — Graph Theory · eulerian-walks-digraphs

Problem

Prove Theorem 4.7.2. (Theorem 4.7.2 states: Let DD be a weakly connected multidigraph. Then: (a) The multidigraph DD has an Eulerian circuit if and only if each vertex vv of DD satisfies deg⁡+v=deg⁡−v\deg^+ v = \deg^- v. (b) The multidigraph DD has an Eulerian walk if and only if all but two vertices vv of DD satisfy deg⁡+v=deg⁡−v\deg^+ v = \deg^- v, and the remaining two vertices vv satisfy ∣deg⁡+v−deg⁡−v∣≤1|\deg^+ v - \deg^- v| \leq 1.)

Browse the problem library