To find a Eulerian cycle in a balanced strongly connected gr

To find a Eulerian cycle in a balanced, strongly connected graph, it\'s suggested to start from a vertex with high indegree (and high outdegree). What is the rationale? Assuming you start from the vertex with the highest indegree in the graph, is it always true that the first cycle you get is a Eulerian cycle? Justify your answer.

Solution

A Euler cycle of a directed graph is a cycle that visits every edge of the graph exactly once. If a graph has a Euler cycle, then it is called Eulerian. A directed graph has a Euler cycle if it is strongly connected(one can reach any vertex strating from any other vertex by traversingthe edges in the derection in which they point) and balanced(At every vertex, the indegree and the outdegree are the same).

In view of the above hypothesis, to constuct a Euler cycle in a directed graph, one can start at any vertex, visit all other vetices and finally reache the same vertex where he/she started the cycle. Each time we visit a vertex, a new inward edge should be used and each time we are leaving a vertex, a new outward edge should be used. At the time of finishing the cycle at the same starting vertex, the strating outward edge will be compensated by the final inward edge.

One may reach each vertex once and finish a cycle at the same staring vertex but it may or may not traverse all the edges. Therefor the cycle is not Euler. This cycle will use one inward edge and one outward edge at every vertex but leaves the remaining edge of the vertecies. Hence the first cycle obtained may not be a Euler cycle. Therefore, it is always not true that the first cycle we get is a Euler cycle.