Question: count the total number of Eulerian trails of graph

 I'm thinking about a question about counting the total number of Eulerian trails of following graphs . 

The Seven Bridges in Gonisburg lost one bridge due to war. 

G-e7

We looked up on Wikipedia to  add some details..

For the existence of Eulerian trails it is necessary that zero or two vertices have an odd degree; this means the Königsberg graph is not Eulerian. If there are no vertices of odd degree, all Eulerian trails are circuits. If there are exactly two vertices of odd degree, all Eulerian trails start at one of them and end at the other. A graph that has an Eulerian trail but not an Eulerian circuit is called semi-Eulerian.

It's easy to know that G-e7 is semi-Eulerian. So I want find all Eulerian trails. A simple attempt, found the following one in graph (Pink label).

I feel a little tricky dealing with this through Maple. The first reason is that the Maple graph theory package does not support parallel edges. Unfortunately, eand e6 are parallel edges of G-e7.

To take a step back, what if there are no parallel edges? For considering G-e7-e6.

There are some built-in commands related like FindEulerianPath , but can only find a Euler circuits.

 

 

 

 

Please Wait...