Euler's Circuit Theorem
Theorem. A pseudograph has a circuit containing all edges and vertices if it is connected and every vertex has even degree.
Proof. This proof is by induction on the number n of vertices.
Base case of n = 1. Follow the loops in succession.
Assume for n and prove for a pseudograph of n+1 vertices. Now pick a vertex. Since the degree is even, you can pair the incident edges, and you can avoiding pairing the two ends of a loop. Shortcut each pair to avoid the vertex and delete it. By induction, each component of the new pseudograph has the desired circuit. Then restore the vertex and undo the shortcuts to obtain the desired circuit.
Leave Euler's Circuit Theorem to:
Best Posts From axiogenesis
We have not curated any of axiogenesis's posts yet. But you can encourage our curation team to review posts by visiting them regularly and by referring other readers. Because we give priority to frequently read content.