Can You Draw It In One Go?

Bangladeshi children in 80’s used to play a game with pencil and paper. Whether a certain figure can be redrawn with one go, that is, without lifting up the pencil and not going over any line again. For example, outline of a hat is simply drawn with edges and a kid is asked to redraw the same by using the pencil on the page in one go. Starting point can be anyone. Actually it is not possible to draw a hat as shown on figure though it looks pretty simple. On the other hand the oriental drum, shown in the figure, can be drawn in one go even it doesn’t look so easy. What is the catch here?

Graph Theory

The Mathematics behind this problem of drawing in one go is Graph Theory. Mathematicians have worked and been working on this for solving many real life problems so far. The problems may be simple and small like this kids’ drawing puzzle. Sometimes the problems are so complicated that computer programs are necessary to process its huge volume of calculations. The Graph Theory is credited to a Swiss Mathematician Leonard Euler (1707-1783) who first wrote a scholarly article on Graph Theory relating to a bridge problem called Konigsberg Bridge Puzzle. Later this was well accepted as a significant branch in Mathematics.  A graph is actually a system of points with some specific connections. Graph is not same as chart sometimes people get confused with. Graph expresses relationships amongst points, such as, computer network at an office or road communication among cities of a state. Here each of the cities or points is called a vertex and each connecting road or line is called an edge. In a graph, every point may not have equal number of edges. A sequence of vertices along with their edges is called a path. A circuit can be made when a path starts from a point and ends at the same.  Eulerian Path of a graph crosses all the edges of a graph by reaching vertices one after another, but no edge is crossed more than once.  Eulerian Circuit is the Eulerian Path, which starts from and ends at a same vertex.

Solution

Graphs

To draw a figure (graph) in one go, there must exist a Eulerian Circuit for the graph. It is possible if and only if each vertex of that graph has even degrees. In the given figure, the flower graph can be presented as {8, 2, 2, 2, 2, 2, 2, 2, 2, 2} in which each and every vertex has even number of degrees. So one can start from any point and move through edges and come back at the starting point in one go. This is Eulerian graph because there exists the Eulerain Circuit. Similarly, a graph can be called semi-Eulerian if there exists only a Eulerian Path. Eulerian Path may exist in a graph when there are only two vertices with odd degrees. The hat {3, 3, 2, 2, 2, 2} is an example of semi-Eulerian graph, where one can start from an odd degree vertex, A or B in this case, and reach at the other by crossing all the edges only once; without lifting the pencil up. In our given figure, the house is a {3, 3, 3, 3, 2, 2, 2} graph in which there are more than two odd degree vertices. As a result, this house can not be drawn in one go because there does not exist Eulerian Circuit or Eulerian Path in this graph according to the Graph Theory.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s