 FindEulerianCycle - Maple Help

GraphTheory

 IsEulerian
 test if graph is Eulerian
 FindEulerianCycle
 find Eulerian cycle
 FindEulerianPath
 find Eulerian path Calling Sequence IsEulerian(G) IsEulerian(G, T) FindEulerianCycle(G) FindEulerianPath(G) Parameters

 G - graph T - (optional) name Description

 • The IsEulerian command returns true if the input graph is an Eulerian graph, i.e there exists a Eulerian cycle, a closed walk in the graph that traverses each edge exactly once. It returns false otherwise.
 • An Eulerian path is a walk that traverses each edge exactly once, but whose initial and final vertices are not required to be the same. Every Eulerian cycle is an Eulerian path, but the reverse is not true.
 • An optional second argument T is assigned a Trail corresponding to an Eulerian cycle of the graph if such a cycle exists, and FAIL otherwise.
 • The FindEulerianCycle command returns a trail corresponding to an Eulerian cycle if one exists, and NULL otherwise.
 • The FindEulerianPath command returns a list corresponding to an Eulerian path if one exists, and NULL otherwise.
 • The algorithm used to construct the trail is depth-first-search. The complexity is $\mathrm{O}\left(n+m\right)$ where n=|V| and m=|E|. Eulerian graphs in SpecialGraphs

 • The following are graphs in the SpecialGraphs subpackage which are Eulerian.

 Graph Number of Vertices Number of Edges 5 6 6 12 12 24 16 32 16 48 19 38 20 40 21 42 27 54 27 216 52 104 56 280 57 171 63 183 70 140 77 616 81 810 100 1100 100 1800 231 3465 243 2673 275 15400 1782 370656 Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{IsEulerian}\left(\mathrm{CompleteGraph}\left(4\right)\right)$
 ${\mathrm{false}}$ (1)
 > $\mathrm{IsEulerian}\left(\mathrm{CompleteGraph}\left(5\right),'T'\right)$
 ${\mathrm{true}}$ (2)
 > $T$
 ${\mathrm{Trail}}{}\left({1}{,}{2}{,}{3}{,}{1}{,}{4}{,}{2}{,}{5}{,}{3}{,}{4}{,}{5}{,}{1}\right)$ (3)
 > $\mathrm{FindEulerianPath}\left(\mathrm{SpecialGraphs}:-\mathrm{BookGraph}\left(3\right)\right)$
 $\left[{1}{,}{2}{,}{4}{,}{3}{,}{1}{,}{5}{,}{6}{,}{2}{,}{8}{,}{7}{,}{1}\right]$ (4) Compatibility

 • The GraphTheory[FindEulerianCycle] and GraphTheory[FindEulerianPath] commands were introduced in Maple 2020.