Function Repository Resource:

EulerizeGraph

Source Notebook

Add edges to a graph to make it Eulerian

Contributed by: Peter Burbery

ResourceFunction["EulerizeGraph"][graph]

adds edges to a connected graph to make it Eulerian.

Details

An Eulerian graph is also referred to as unicursal.

A graph is Eulerian if it contains a path through all edges with no repetitions.

If the input graph is already Eulerian, it is returned unchanged.

Examples

Basic Examples (2)

Create the bridges of Königsberg graph:

In[1]:=

$islands = {\[ScriptCapitalT], \[ScriptCapitalL], \[ScriptCapitalM], \[ScriptCapitalR]}; bridges = {\[ScriptCapitalL] \[UndirectedEdge] \[ScriptCapitalM], \[ScriptCapitalL] \[UndirectedEdge] \[ScriptCapitalM], \[ScriptCapitalT] \[UndirectedEdge] \[ScriptCapitalM], \[ScriptCapitalT] \[UndirectedEdge] \[ScriptCapitalM], \[ScriptCapitalM] \[UndirectedEdge] \[ScriptCapitalR], \[ScriptCapitalR] \[UndirectedEdge] \[ScriptCapitalT], \[ScriptCapitalR] \[UndirectedEdge] \[ScriptCapitalL]}; bridgesOfKonigsbergSystem = Graph[islands, bridges, VertexLabels -> "Name"]$

Out[3]=

Eulerize the Königsberg graph:

In[4]:=

Out[4]=

Eulerize the graph corresponding to the modern-day bridges of Königsberg (some of the original bridges are no longer present):

In[5]:=

$Konigsburg2022 = Graph[islands, {\[ScriptCapitalL] \[UndirectedEdge] \[ScriptCapitalR], \[ScriptCapitalR] \[UndirectedEdge] \[ScriptCapitalM], \[ScriptCapitalT] \[UndirectedEdge] \[ScriptCapitalM], \[ScriptCapitalM] \[UndirectedEdge] \[ScriptCapitalL], \[ScriptCapitalR] \[UndirectedEdge] \[ScriptCapitalT]}, VertexLabels -> "Name"]; Row[{Konigsburg2022, ResourceFunction["EulerizeGraph"][Konigsburg2022]}]$