![](\"\/..\/images\/graph00_jun26_2016.png\")
<\/p>\nAn Euler circuit is a route through a graph that travels every edge exactly once, then ends where it started. If a graph is connected, with every vertex of even degree, then it has an Euler circuit. Following is a proof by induction:<\/p>\n
First of all, consider the graph below. Each vertex has degree two; clearly A → B → C → D → A is an Euler circuit.<\/p>\n
<\/p>\n
Adding vertex E, we might end up with the graph<\/p>\n
![](\"\/..\/images\/graph0_jun26_2016.png\")
<\/p>\n
To connect to point E, vertices B and D now have odd degree (3). Therefore, they need to be increased to degree 4. The simplest way is to join them by segment BD, seen in the next graph.<\/p>\n
![](\"\/..\/images\/graph_jun26_2016.png\")
<\/p>\n
Now, the original Euler circuit A → B → C → D → A can be interrupted in the middle as follows: A → B → E → D → B <\/span> → C → D → A. The result is an Euler circuit on the graph with an added vertex.<\/p>\n On a graph of n vertices, each with degree 2, an Euler circuit is apparent. When a vertex is added outside that circuit, adding other edges as well to bring the vertices back to even, the graph can be eventually reduced to one or more situations like the one(s) above.<\/p>\n I’ll be discussing more graph theory ideas:)<\/p>\n Source:<\/p>\n Grimaldi, Ralph P. Discrete and Combinatorial Mathematics<\/u>. Don Mills:
Addison-Wesley, 1994.<\/p>\n