Introduction to Graph Theory · Problem 4.10

Digraphs and multidigraphs — Darij Grinberg

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.)
Intuitive explanation

An Eulerian circuit or walk must traverse every edge exactly once, which means at each vertex you enter and leave the same number of times. The key insight is that in-degree and out-degree balance directly encodes this traversal property: balanced degrees mean you can always leave a vertex after entering it, while specific imbalances at exactly two vertices allow a walk with a defined start and end. Think of degree conditions as the "traffic flow" constraint—they tell you whether a continuous path through all edges is even possible.

Intuitive explanation

An Eulerian circuit or walk must traverse every edge exactly once, which means at each vertex you enter and leave the same number of times. The key insight is that in-degree and out-degree balance directly encodes this traversal property: balanced degrees mean you can always leave a vertex after entering it, while specific imbalances at exactly two vertices allow a walk with a defined start and end. Think of degree conditions as the "traffic flow" constraint—they tell you whether a continuous path through all edges is even possible.

Browse the problem library