Function Repository Resource:

# SemiEulerianGraphQ

Test if a connected undirected graph is semi-Eulerian

Contributed by: Peter Cullen Burbery
 ResourceFunction["SemiEulerianGraphQ"][g] yields True if the connected undirected graph g is semi-Eulerian and False otherwise.

## Details

A graph is semi-Eulerian if it is possible to traverse the graph crossing each edge exactly once without backtracking or retracing your steps if you can start and stop at different vertices.
ResourceFunction["SemiEulerianGraphQ"] also works for multigraphs.

## Examples

### Basic Examples (3)

Construct a graph with only two odd vertices:

 In[1]:=
 Out[1]=
 In[2]:=
 Out[2]=

Test if the graph is semi-Eulerian:

 In[3]:=
 Out[3]=

Test if the graph is also Eulerian:

 In[4]:=
 Out[4]=

A graph with no odd vertices:

 In[5]:=
 Out[5]=
 In[6]:=
 Out[6]=

The graph is semi-Eulerian and Eulerian:

 In[7]:=
 Out[7]=
 In[8]:=
 Out[8]=

A graph with more than two odd vertices:

 In[9]:=
 Out[9]=
 In[10]:=
 Out[10]=

The graph is neither semi-Eulerian nor Eulerian:

 In[11]:=
 Out[11]=
 In[12]:=
 Out[12]=

### Scope (2)

Test if a buckyball graph is semi-Eulerian:

 In[13]:=
 Out[13]=

Test if a torus graph is semi-Eulerian:

 In[14]:=
 Out[14]=

### Neat Examples (1)

The multigraph representing the bridges of Königsberg is not semi-Eulerian:

 In[15]:=
 Out[15]=
 In[16]:=
 Out[16]=

Peter Burbery

## Version History

• 1.0.0 – 29 August 2022

## Author Notes

I might add a way to test if a directed graph and mixed graph is semi Eulerian in the future.