When I was a Child my sister asked me to draw this pentagon shape house but there was a condition. What is that? The condition was that I can not lift my pencil. After trying different options I surrendered myself to my sister and she showed me this cool trick to draw the house without lifting the pencil. So why on earth really I am sharing this story?

So how would you know if you can draw something like this without lifting your pencil.?Or more precisely how would you cross some path without crossing it more than once or is it even possible in the first place??? Leonhard Euler , a Swiss mathematician had this question answered almost more than 200 years ago. So the generalized idea is ,

An

Euler Pathis apaththat goes through every edge of a graph exactly once AnEuler Circuitis anEuler Path

Doesn’t really make much sense? Just keep going it shall be making sense soon. For that, we need to know what is **edge** and what is **vertex!**

The pointy head or the junction that joints two line together is vertex or vertexes. In the context of **graph theory **here **A , B ,C , D, E each joints are vertex** . And the **path or line that joint them are called edges**, for example edge of D vertex is DE and DC . If it helps and you would like to compare it with a computer networking system in the physical level , vertexes are the nodes and edges are the wires that connecting them . Ok, so now we understand what is vertex and what is edge . So what are the use of them in this concept?

Our core problem was we have to draw this house without lifting the pencil, in the same way we could say that if we can travel all the paths or edges without crossing them once then we can achieve our goal. And if we are successful doing it then this circuit is Eulerian Circuit and the path we used is **Eulerian Path . **So how would we conclude if a circuit has eulerian path or not? So, *if more than two vertices ( vertexes are also named as vertices ) have an odd number of edges then that circuit won’t have Eulerian Path .*

In the blue house drawn above **D vertex** has **2 edges** , DE and DC . **E vertex** has **4 edges** ED , EC , EB , EA . **A vertex** has **3 edges** AE , AC, AB . **B vertex **has **3 edges** as well BA , BE , BC **. C vertex** has **4 edges** CB , CA , CE , CD .

So , only A and B has an odd number of edges and the rest three vertex have an even number of edges. So it is an Eulerian path. This also means that you can travel all the paths without crossing a path more than once. And one important thing to notice is that the start of the traveling would **start and end in an odd vertex**. In this context, the start and end both has to be in either A or B vertex. Because only in odd vertex it is possible to start, travel and end. It requires three cases. Therefore, the bottom line is whenever we see something like a circuit we should try to imagine it in the context of graph. Then see if the nodes have more than 2 vertex where they have odd number of edges. Then like my sister asked me to play that trick in that childhood you could possibly conclude into a decision faster that whether or not it’s possible to complete the route without traveling it more than once.

The ** Eulerian Path is an important concept of Graph Theory** . In computer science graph theory is an important aspect of thinking algorithmically. Computer scientists like to think of everything as a graph. Not the graph of x-axis and y-axis, these graphs are a little more complex than that . You can compare the above example with anything in your real life application,i.e. Computer networking where the networking engineer has to figure out the best way of meshing the nodes or devices , the traffics or the google map you use in your phone also use Graph Theory in its backbone.