[Math] How to find Eulerian path in the given graph

Question

I have plotted the following graph (was given by the adjacency matrix):

And I have to find the Eulerian path there and emphase this.

I am concerned because my book says that the further action depend on the initial graph.
For instance if we have countier or cycle in the initial graph we can start in any vertex.
If the initial graph has a chain we should start from any vertex which power is odd.
If the initial graph has a chain, a start vertex depends on vertex's degree and so on.

But how can I figure out if there's a chain, a countier or a cycle in a graph and how should I proceed afterwards?

Answer 1

You should start by looking at the degrees of the vertices, and that will tell you if you can hope to find:

• an Eulerian tour (some say "Eulerian cycle") that starts and ends at the same vertex,
• or an Eulerian walk (some say "Eulerian path") that starts at one vertex and ends at another,
• or neither.

The idea is that in a directed graph, most of the time, an Eulerian whatever will enter a vertex and leave it the same number of times. So the in-degree and the out-degree must be equal. (The exception is the start or the end of an Eulerian walk, where they can be off by one.)

Here, most vertices have the same in-degree and out-degree, which is promising, but vertex $4$ has two edges going out and only one going in, and vertex $6$ has two edges going in and only one going out.

This means that to balance the edges going in and out of the vertices, you should start at vertex $4$ and end at vertex $6$.