Eulerian Cycle

Author

Eric W. Weisstein
February 2, 2024

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/EulerianCycle.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/EulerianCycle.html.

©2024 Wolfram Research, Inc. except for portions noted otherwise

Special classes

Empty

bug(333162)

FindEulerianCycle[System`Graph[{1},{}]]

FindEulerianCycle[System`Graph[{1},{}],All]

Table[FindEulerianCycle[System`Graph[Range[n],{}]],{n,0,5}]

Table[FindHamiltonianCycle[System`Graph[Range[n],{}]],{n,0,5}]

Table[FindEulerianCycle[KnightTourGraph[n,n]],{n,8}]

FindEulerianCycle[GraphDisjointUnion@@Table[PathGraph[{1,2}],2]]

FindEulerianCycle[GraphDisjointUnion[PathGraph[{1,2}],System`Graph[{1,2},{}]]]

Select[GraphData[;;10],FindEulerianCycle[GraphData[#]]==={{}}&]

FindEulerianCycle[GraphData[{4,6}]]

GraphData[{4,6},"Graph","Labeled"]

Platonic

GraphData[{"Platonic","Eulerian"}]

e=Partition[EulerianCycle[Graph["OctahedralGraph"]],2,1]

nest=Reverse[NestList[Most,e,11]]

rules=Thread[Range[GraphData["OctahedralGraph","V"]]->GraphData["OctahedralGraph","VertexCoordinates"]]

Graphics[Arrow/@(e/.rules)]

GraphicsGrid[Partition[Graphics[{GraphData["OctahedralGraph"][[1]],Blue,Thickness[.01],Arrowheads[Medium],Arrow/@#/.rules},PlotRange->{{-1.3,1.3},{-.9,1.45}}]&/@nest,4,4,{1,1},{}],ImageSize->400]

GraphicsGrid[Partition[ShowGraph[Highlight[Graph["OctahedralGraph"],{#}]]&/@rules,4,4,{1,1},{}]]

Archimedean

GraphData[{"Archimedean","Eulerian"}]

Table

GraphDataCountTable["EulerianCycleCount",{"Antiprism"->297384,"Book"->009445,"CocktailParty"->297383,"Complete"->369820,"Dipyramid"->369822,"DorogovtsevGoltsevMendes"->369821,"SierpinskiGasket"->298202,"Sun"->297386,"TorusGrid"->297385,"TriangularGrid"->297387,"TriangularSnake"->000079}]

Parametrized families

<<MathWorld`Graphs`

Andrasfai

seq=Table[GraphData[{"Andrasfai",n},"EulerianCycleCount"],{n,10}]

n==6 needs > 300 GB

Antiprism

A297384

Entity["Graph",{"Antiprism",n}]["EulerianCycleCount"]

seq=Table[GraphData[{"Antiprism",n},"EulerianCycleCount"],{n,3,25}]

FindLinearRecurrence[DeleteMissing@seq]

seq=LinearRecurrence[{13,-48,52,-16},{4,44,372,2932},20]

FullSimplify[FindSequenceFunction[DeleteMissing@seq,n],n∈Integers]

Table[(((4-2 (Sqrt[3])))^n)+(((2 (2+(Sqrt[3]))))^n),{n,10}]//Expand

FindSequenceFunction[%,n]

Table[(((4-2 (Sqrt[3])))^n)+(((4+2 (Sqrt[3])))^n)-(2/3) (2+(4^n)),{n,20}]//Expand

Table[(2^n)((((2- (Sqrt[3])))^n)+(((2+(Sqrt[3])))^n))-(2/3) (2+(4^n)),{n,20}]//Expand

Table[2/3*(2+4^n),{n,20}]

Table[((((2- (Sqrt[3])))^n)+(((2+(Sqrt[3])))^n)),{n,20}]//Expand

Table[LucasL[2n,Sqrt[2]],{n,20}]//Round

Table[(2^n)LucasL[2n,Sqrt[2]]-(2/3) (2+(4^n)),{n,20}]//Round

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

CoefficientList[Series[-((4(-1+2 x+2 (x^2)))/(1-13 x+48 (x^2)-52 (x^3)+16 (x^4))),{x,0,20}],x]

Apollonian

seq=Table[GraphData[{"Apollonian",n},"EulerianCycleCount"],{n,6}]

Barbell

seq=Table[GraphData[{"Barbell",n},"EulerianCycleCount"],{n,3,20}]

Bishop n×n

seq=Table[GraphData[{"Bishop",{n,n}},"EulerianCycleCount"],{n,10}]

BlackBishop n×n

seq=Table[GraphData[{"BlackBishop",{n,n}},"EulerianCycleCount"],{n,10}]

Book

seq=Table[GraphData[{"Book",n},"EulerianCycleCount"],{n,20}]

FindSequenceFunction[DeleteMissing@seq[[;;;;2]],(n+1)/2]//FullSimplify

Table[Piecewise[{{0,Mod[n,2]==0},{n!,Mod[n,2]==1}}],{n,20}]

Centipede

seq=Table[GraphData[{"Centipede",n},"EulerianCycleCount"],{n,10}]

CocktailParty

A297383

seq=Table[GraphData[{"CocktailParty",n},"EulerianCycleCount"],{n,20}]

Complete

A369820

Entity["Graph",{"Complete",n}]["EulerianCycleCount"]

Table[Length[FindEulerianCycle[System`CompleteGraph[n],All]],{n,7}]//Timing

seq=Table[GraphData[{"Complete",n},"EulerianCycleCount"],{n,20}]

seq[[1;;;;2]]

A007082

http://users.cecs.anu.edu.au/~bdm/papers/euler.pdf

Length[e={2,264,1015440,90449251200,169107043478365440,6267416821165079203599360,4435711276305905572695127676467200,58393052751308545653929138771580386824519680,14021772793551297695593332913856884153315254190271692800,60498832138791357698014788383803842810832836262245623803123983974400}/2]

MapIndexed[#((((#2[[1]]-1)!))^(2#2[[1]]+1))&,e]

Table[(2^((n+1)/2))(π^(1/2))(E^(-(n^2)/2+11/12))(n^((n-2)(n+1)/2))/2,{n,3,21,2}]//Round

CompleteBipartite m×n

Entity["Graph",{"CompleteBipartite",{m,n}}]["EulerianCycleCount"]

Block[{m,n},DeleteCases[{
#,
{m,n}=("CompleteBipartite"/.GraphData[#,"NotationRules"]);If[Mod[m,2]==1||Mod[n,2]==1,0,XXX],
GraphData[#,"EulerianCycleCount"]
}&/@GraphData["CompleteBipartite"],{_,x_,x_}|{_,_,_Missing}]]

Table[(2n+1)!,{n,5}]

rules=Table[{"CompleteBipartite",{2,n}}->(n-1)!,{n,4,20,2}]

CompleteBipartite n×n

Entity["Graph",{"CompleteBipartite",{n,n}}]["EulerianCycleCount"]

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"EulerianCycleCount"],{n,20}]

n==6 needs 300+ GB

CompleteTripartite k×m×n

Entity["Graph",{"CompleteTripartite",{k,m,n}}]["EulerianCycleCount"]

CompleteTripartite n×n×n

Entity["Graph",{"CompleteTripartite",{n,n,n}}]["EulerianCycleCount"]

seq=Table[GraphData[{"CompleteTripartite",{n,n,n}},"EulerianCycleCount"],{n,10}]

n==3 needs 300+ GB

FindLinearRecurrence[DeleteMissing@seq]

FindGeneratingFunction[seq,x]//Head//Timing

CrossedPrism

seq=Table[GraphData[{"CrossedPrism",2n},"EulerianCycleCount"],{n,2,10}]

Crown

seq=Table[GraphData[{"Crown",n},"EulerianCycleCount"],{n,3,20}]

n==7 needs 300+ GB

CubeConnectedCycle

Entity["Graph",{"CubeConnectedCycle",n}]["EulerianCycleCount"]

seq=Table[GraphData[{"CubeConnectedCycle",n},"EulerianCycleCount"],{n,3,8}]

Cycle

Entity["Graph",{"Cycle",n}]["EulerianCycleCount"]

seq=Table[GraphData[{"Cycle",n},"EulerianCycleCount"],{n,3,20}]

Dipyramid

A369822

seq=Table[GraphData[{"Dipyramid",n},"EulerianCycleCount"],{n,3,20}]

DorogovtsevGoltsevMendes

A369821

seq=Table[GraphData[{"DorogovtsevGoltsevMendes",n},"EulerianCycleCount"],{n,0,7}]

Empty

Entity["Graph",{"Empty",n}]["EulerianCycleCount"]

seq=Table[GraphData[{"Empty",n},"EulerianCycleCount"],{n,30}]

FibonacciCube

seq=Table[GraphData[{"FibonacciCube",n},"EulerianCycleCount"],{n,15}]

FoldedCube

seq=Table[GraphData[{"FoldedCube",n},"EulerianCycleCount"],{n,2,10}]

n==6 needs 300+ GB

Gear

seq=Table[GraphData[{"Gear",n},"EulerianCycleCount"],{n,3,20}]

Grid m×n

Entity["Graph",{"Grid",{m,n}}]["EulerianCycleCount"]

Block[{m,n},DeleteCases[{
{m,n}=PadLeft["Grid"/.GraphData[#,"NotationRules"],2,1],
Piecewise[{{1,m==n==2}},0],
GraphData[#,"EulerianCycleCount"]}&/@Select[GraphData["Grid"],Head@FirstCase[GraphData[#,"StandardNames"],{"Grid",{_,_}}]=!=Missing&],{_,x_,x_}]]

Grid n×n

Entity["Graph",{"Grid",{n,n}}]["EulerianCycleCount"]

seq=Table[GraphData[{"Grid",{n,n}},"EulerianCycleCount"],{n,10}]

Grid k×m×n

Entity["Graph",{"Grid",{k,m,n}}]["EulerianCycleCount"]

Block[{k,m,n},DeleteCases[{
{k,m,n}=PadLeft["Grid"/.GraphData[#,"NotationRules"],3,1],
Piecewise[{{1,(k==m==2||m==n==2||n==k==2)&&Min[k,m,n]==1}},0],
GraphData[#,"EulerianCycleCount"]}&/@Select[GraphData["Grid"],Head@FirstCase[GraphData[#,"StandardNames"],{"Grid",{_,_,_}}]=!=Missing&],{_,x_,x_}]]

Grid n×n×n

Entity["Graph",{"Grid",{n,n,n}}]["EulerianCycleCount"]

seq=Table[GraphData[{"Grid",{n,n,n}},"EulerianCycleCount"],{n,10}]

HalvedCube

seq=Table[GraphData[{"HalvedCube",n},"EulerianCycleCount"],{n,10}]

Hanoi

seq=Table[GraphData[{"Hanoi",n},"EulerianCycleCount"],{n,5}]

Helm

seq=Table[GraphData[{"Helm",n},"EulerianCycleCount"],{n,3,10}]

Hypercube

Entity["Graph",{"Hypercube",n}]["EulerianCycleCount"]

seq=Table[GraphData[{"Hypercube",n},"EulerianCycleCount"],{n,10}]

Keller

Entity["Graph",{"Keller",n}]["EulerianCycleCount"]

seq=Table[GraphData[{"Keller",n},"EulerianCycleCount"],{n,5}]

King m×n

DeleteCases[{
mn="King"/.GraphData[#,"NotationRules"],
0,
GraphData[#,"EulerianCycleCount"]}&/@GraphData["King"],{_,x_,x_}]

King n×n

Table[GraphData[{"King",{n,n}},"EulerianCycleCount"],{n,10}]

Knight m×n

Entity["Graph",{"Knight",{m,n}}]["EulerianCycleCount"]

Block[{m,n},DeleteCases[{
#,
{m,n}=("Knight"/.GraphData[#,"NotationRules"]);If[m==n==3,1,0],
GraphData[#,"EulerianCycleCount"]
}&/@GraphData["Knight"],{_,x_,x_}]]

Knight n×n

Entity["Graph",{"Knight",{n,n}}]["EulerianCycleCount"]

Table[GraphData[{"Knight",{n,n}},"EulerianCycleCount"],{n,20}]

Ladder

Entity["Graph",{"Ladder",n}]["EulerianCycleCount"]

seq=Table[GraphData[{"Ladder",n},"EulerianCycleCount"],{n,20}]

LadderRung

seq=Table[GraphData[{"LadderRung",n},"EulerianCycleCount"],{n,20}]

MengerSponge

Table[GraphData[{"MengerSponge",n},"EulerianCycleCount"],{n,3}]

MoebiusLadder

Entity["Graph",{"MoebiusLadder",n}]["EulerianCycleCount"]

seq=Table[GraphData[{"MoebiusLadder",n},"EulerianCycleCount"],{n,3,25}]

Mycielski

Entity["Graph",{"Mycielski",n}]["EulerianCycleCount"]

seq=Table[GraphData[{"Mycielski",n},"EulerianCycleCount"],{n,11}]

Odd

Entity["Graph",{"Odd",n}]["EulerianCycleCount"]

seq=Table[GraphData[{"Odd",n},"EulerianCycleCount"],{n,7}]

Pan

seq=Table[GraphData[{"Pan",n},"EulerianCycleCount"],{n,3,20}]

Path

Entity["Graph",{"Path",n}]["EulerianCycleCount"]

seq=Table[GraphData[{"Path",n},"EulerianCycleCount"],{n,20}]

Prism

Entity["Graph",{"Prism",n}]["EulerianCycleCount"]

seq=Table[GraphData[{"Prism",n},"EulerianCycleCount"],{n,3,25}]

Queen m×n

{#,"Queen"/.GraphData[#,"NotationRules"],GraphData[#,"EulerianCycleCount"]}&/@GraphData["Queen"]

Queen n×n

Table[GraphData[{"Queen",{n,n}},"EulerianCycleCount"],{n,10}]

Rook m×n

DeleteCases[{"Rook"/.GraphData[#,"NotationRules"],GraphData[#,"EulerianCycleCount"]}&/@GraphData["Rook"],{_,x_,x_}]

Rook n×n

Table[GraphData[{"Rook",{n,n}},"EulerianCycleCount"],{n,10}]

RookComplement n×n

Table[GraphData[{"RookComplement",{n,n}},"EulerianCycleCount"],{n,10}]

SierpinskiCarpet

seq=Table[GraphData[{"SierpinskiCarpet",n},"EulerianCycleCount"],{n,4}]

SierpinskiGasket

A298202

seq=Table[GraphData[{"SierpinskiGasket",n},"EulerianCycleCount"],{n,5}]

NestList[Function[{e,f,g},{16e^3+48f e^2,3e^3+(32f+8g)e^2+56f^2 e,e^3+(30f+12g)e^2+(156f^2+96g f)e+112f^3}]@@#&,{1,0,0},5][[All,1]]

SierpinskiTetrahedron

seq=Table[GraphData[{"SierpinskiTetrahedron",n},"EulerianCycleCount"],{n,6}]

Star

Entity["Graph",{"Star",n}]["EulerianCycleCount"]

Table[GraphData[{"Star",n},"EulerianCycleCount"],{n,25}]

Sun

A297386

seq=Table[GraphData[{"Sun",n},"EulerianCycleCount"],{n,3,20}]

Sunlet

seq=Table[GraphData[{"Sunlet",n},"EulerianCycleCount"],{n,3,20}]

Tetrahedral

seq=Table[GraphData[{"Tetrahedral",n},"EulerianCycleCount"],{n,6,10}]

Torus Grid m×n

A298117

Table[GraphData[{"TorusGrid",{m,n}},"EulerianCycleCount"],{n,3,10},{m,3,n}]//Column//TraditionalForm

data=Import["https://oeis.org/A291872/b298117.txt","Table"][[All,2]];

data={2,4,4,8,40,8,16,320,320,16,32,2368,8616,2368,32,64,16832,207496,207496,16832,64,128,116608,4788808,15639936,4788808,116608,128,256,793088,108326760,1116199200,1116199200,108326760,793088,256};

Table[data[[Binomial[i,2]+(1/2) (j-1) (2 i+j)+1]],{i,10},{j,i}]/._Part:>Missing["NotAvailable"]//Quiet//Column

rules=Select[Flatten[MapIndexed[GraphData[{"TorusGrid",Sort[#2]},"#"]->#&,Take[#,{3,-2}]&/@ImportString[StringDrop["
1  |  2      4         8          16             32                64 ...
2  |  4     40       320        2368          16832            116608 ...
3  |  8    320      8616      207496        4788808         108326760 ...
4  | 16   2368    207496    15639936     1116199200       77643032832 ...
5  | 32  16832   4788808  1116199200   242230440480    50917973008584 ...
6  | 64 116608 108326760 77643032832 50917973008584 32098460087825856 ...",1],"Table"],{2}]],FreeQ[GraphData]]//Union//Quiet

TorusGrid 3×n

A282621

Table[GraphData[{"TorusGrid",Sort[{3,n}]},"EulerianCycleCount"],{n,3,10}]

FullSimplify[SeriesCoefficient[8*x*(1-7*x-61*x^2+202*x^3)/((1-2*x)*(1-4*x)*(1-5*x)*(1-14*x)*(1-22*x)),{x,0,n}],n>0]

seq=Table[(22^n)+(1/3) ((2^n)+3 (2^(1+2 n))-8 (5^n)-(2^(1+n)) (7^n)),{n,20}]

FindLinearRecurrence[seq]

LinearRecurrence[{47,-742,4796,-13144,12320},{8,320,8616,207496,4788808},20]

CoefficientList[Series[8(1-7x-61x^2+202x^3)/((1-2x)(1-4x)(1-5x)(1-14x)(1-22x)),{x,0,20}],x]

TorusGrid 4×n

A298197

Table[GraphData[{"TorusGrid",Sort[{4,n}]},"EulerianCycleCount"],{n,3,10}]

seq={16,2368,207496,15639936,1116199200,77643032832,5318859987584,360460090519552,24225364155392512,1617040095771160576,107318756823774554112,7087408485751290626048,466051677657117523779584,30530955397986792883159040,1993388935416599069605396480};

FindSequenceFunction[seq,n]//Head//Timing

FindLinearRecurrence[seq]//Head//Timing

FindGeneratingFunction[seq,x]//Head//Timing

FullSimplify[SeriesCoefficient[8*x*(2-188*x+3321*x^2+177454*x^3-9041760*x^4+171251312*x^5-1590178736*x^6+5597941472*x^7+25225706112*x^8-343839085056*x^9+1466120669184*x^10-2913427243008*x^11+2262128394240*x^12)/((1-2*x)*(1-4*x)*(1-6*x)*(1-10*x)^2*(1-12*x)^2*(1-30*x)*(1-24*x+64*x^2)*(1-66*x+264*x^2)^2),{x,0,n}],n∈Integers&&n>0]

Table[-(((((12-4 (Sqrt[5])))^n)-(((12+4 (Sqrt[5])))^n))/(4(Sqrt[5]))),{n,10}]//Expand

seq=Table[(1/4) (-4 (((12-4 (Sqrt[5])))^n)-4 (((12+4 (Sqrt[5])))^n)+(2^n) (-3+3 (2^(1+n))+(3^n)+(5^n)-(15^n))+2 (((33-5 (Sqrt[33])))^n)+2 (((33+5 (Sqrt[33])))^n))+(1/330) (-11 (2^n) (6 (5^n)+5 (6^n))+50 (((33-5 (Sqrt[33])))^n)+50 (((33+5 (Sqrt[33])))^n)) n,{n,60}]//Expand;

coef=FindLinearRecurrence[seq]

Length[coef]

Take[seq,Length[coef]]

LinearRecurrence[{242,-24508,1377576,-48319952,1127281504,-18164303168,206564578176,-1673816120832,9654475382784,-39144748253184,108479226544128,-194648732467200,202715666841600,-92493840384000},{16,2368,207496,15639936,1116199200,77643032832,5318859987584,360460090519552,24225364155392512,1617040095771160576,107318756823774554112,7087408485751290626048,466051677657117523779584,30530955397986792883159040},21]

CoefficientList[Series[8(2-188x+3321x^2+177454x^3-9041760x^4+171251312x^5-1590178736x^6+5597941472x^7+25225706112x^8-343839085056x^9+1466120669184x^10-2913427243008x^11+2262128394240x^12)/((1-2x)(1-4x)(1-6x)(1-10x)^2(1-12x)^2(1-30x)(1-24x+64x^2)(1-66x+264x^2)^2),{x,0,20}],x]

TorusGrid n×n

A297385

Table[GraphData[{"TorusGrid",{n,n}},"EulerianCycleCount"],{n,3,10}]

Transposition

Entity["Graph",{"Transposition",n}]["EulerianCycleCount"]

Table[GraphData[{"Transposition",n},"EulerianCycleCount"],{n,5}]

Triangular

seq=Table[GraphData[{"Triangular",n},"EulerianCycleCount"],{n,5,20}]

TriangularGrid

A297387

seq=Table[GraphData[{"TriangularGrid",n},"EulerianCycleCount"],{n,0,10}]

FindLinearRecurrence[Rest@DeleteMissing@Drop[seq,2]]//Head

FindSequenceFunction[DeleteMissing@Drop[seq,2],n-1]//Head

FindGeneratingFunction[DeleteMissing@seq,x]//Head//Timing

TriangularHoneycombAcuteKnight

seq=Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"EulerianCycleCount"],{n,20}]

TriangularHoneycombObtuseKnight

seq=Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"EulerianCycleCount"],{n,4,20}]

TriangularHoneycombQueen

seq=Table[GraphData[{"TriangularHoneycombQueen",n},"EulerianCycleCount"],{n,10}]

FindSequenceFunction[seq,n]

TriangularHoneycombRook

seq=Table[GraphData[{"TriangularHoneycombRook",n},"EulerianCycleCount"],{n,10}]

Web

seq=Table[GraphData[{"Web",n},"EulerianCycleCount"],{n,3,20}]

Wheel

Entity["Graph",{"Wheel",n}]["EulerianCycleCount"]

seq=Table[GraphData[{"Wheel",n},"EulerianCycleCount"],{n,4,20}]

WhiteBishop n×n

seq=Table[GraphData[{"WhiteBishop",{n,n}},"EulerianCycleCount"],{n,2,10}]