Can you explain the definition of “Randomly Eulerian from a vertex v”

graph theory

I just want to understand the following definition:

We define a graph G to be randomly eulerian from a vertex v if every trail of G having initial vertex v can be extended to an eulerian v-v circuit of G.

The following graph is a randomly eulerian from both vertices 4 and 2 but from no others.

I can have a circuit from trail from vertex 0 as initial vertex such as: 01234526740 or 04325476210.
Now, can be extended to an eulerian v-v circuit of G? I don't know what exactly he means here, but we have a circuit for all directions of vertex 0.

Can you explain to me the definition.

Thanks in advance.

Best Answer

A graph is randomly Eulerian if it is impossible to "go wrong", or "get stuck" when trying to make an Eulerian circuit.

For instance, you could start 0476210, and then you'd be stuck, with nowhere to go, but with unused edges. So your graph is not randomly Eulerian from 0.

However, if you start at 4 or 2, it is impossible to go wrong. No matter what you try you can't fail. As long as you never walk the same edge twice, you will always eventually end up with an Eulerian circuit, without having to go back and correct anything. Thus the graph is randomly Eulerian from 2 and from 4.

Related Solutions

[Math] Which of the following graphs has an Eulerian circuit

Here is a $2$-regular graph that is not connected:

             o---o   o---o  
             |   |   |   |  
             o---o   o---o

Your reasoning about (b) and (c) is correct; (c) is the only one that must have an Euler circuit.

[Math] If $G$ is an Eulerian graph with edges $a$, $b$ sharing a vertex $v$, is it true that $G$ has an Eulerian trail in which $a$, $b$ are consecutive

This is not true. For example take a graph which is two cycles and glue them together on a single vertex (namely the number 8), or more specifically the graph

a-b-c-a-d-e-a

There is basically only one Eulerian cycle and in it you cannot travel by c-a-b, because then you will close one cycle and you cannot reach the second one.

Best Answer

Related Solutions

[Math] Which of the following graphs has an Eulerian circuit

[Math] If $G$ is an Eulerian graph with edges $a$, $b$ sharing a vertex $v$, is it true that $G$ has an Eulerian trail in which $a$, $b$ are consecutive

Related Question