Here is a neat way to prove Euler's circuit theorem using induction on the number of vertices. 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.
Congratulations @axiogenesis! You have completed some achievement on Steemit and have been rewarded with new badge(s) :
Click on any badge to view your own Board of Honor on SteemitBoard.
For more information about SteemitBoard, click here
If you no longer want to receive notifications, reply to this comment with the word
STOPDownvoting a post can decrease pending rewards and make it less visible. Common reasons:
Submit