Eulerian Graph

Author

Eric W. Weisstein
February 7, 2024

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

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

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

Graphics

All

With[{width=700,cols=7},GraphicsGrid[Flatten[Partition[#,UpTo[cols]]&/@Map[Show[StyleGraphs[GraphData[#],VertexSize->{"Scaled",.05}],PlotLabel->TextCell[Style[GraphData[#,"Name"],Directive[Italic,Black,FontFamily->"Times"]],TextAlignment->Center,PageWidth->width/cols]]&,DeleteCases[Table[GraphData["Eulerian",n],{n,5}],{}],{2}],1],Dividers->All,ImageSize->width]]

Connected

With[{width=700,cols=7},GraphicsGrid[Flatten[Partition[#,UpTo[cols]]&/@Map[Show[StyleGraphs[GraphData[#],VertexSize->{"Scaled",.05}],PlotLabel->TextCell[Style[GraphData[#,"Name"],Directive[Italic,Black,FontFamily->"Times"]],TextAlignment->Center,PageWidth->width/cols]]&,DeleteCases[Table[GraphData[{"Connected","Eulerian"},n],{n,5}],{}],{2}],1],Dividers->All,ImageSize->width]]

Eulerian Digraphs

Length/@(euleriand=Select[#,EulerianQ]&/@Digraphs/@Range[5])//Timing

ShowGraphArray[Flatten[Map[Partition[#,6,6,{1,1},{}]&,Take[euleriand,4],{1}],1]]

Platonic

EulerianGraphPlot[g_Graph]:=Module[{c=EulerianCycle[g]},
Graphics[{
showGraph[g,PointSize[.05]][[1]],
{RGBColor[1,0,0],(Arrowhead[Vertices[g][[#]]])&/@Partition[c,2,1]}
},AspectRatio->Automatic,PlotRange->All]
]

EulerianQ/@{TetrahedralGraph,CubicalGraph,OctahedralGraph,DodecahedralGraph,IcosahedralGraph}

Octahedral Graph

EulerianCycle[OctahedralGraph]

Show[EulerianGraphPlot[OctahedralGraph]]

GraphDataCountTable

GraphDataCountTable["Eulerian"]

Parametrized families

<<MathWorld`Graphs`

Alkane

seq=Table[GraphData[{"Alkane",n},"Eulerian"],{n,10}]

AlternatingGroupGraph

seq=Table[GraphData[{"AlternatingGroupGraph",n},"Eulerian"],{n,2,6}]

Andrasfai

seq=Table[GraphData[{"Andrasfai",n},"Eulerian"],{n,20}]

Antelope n×n

seq=Table[GraphData[{"Antelope",{n,n}},"Eulerian"],{n,20}]

Antiprism

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

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

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

Apollonian

seq=Table[GraphData[{"Apollonian",n},"Eulerian"],{n,5}]

Barbell

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

BlackBishop n×n

seq=Table[GraphData[{"BlackBishop",{n,n}},"Eulerian"],{n,20}]

Bishop n×n

seq=Table[GraphData[{"Bishop",{n,n}},"Eulerian"],{n,20}]

Book

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

Bruhat

seq=Table[GraphData[{"Bruhat",n},"Eulerian"],{n,6}]

Camel n×n

seq=Table[GraphData[{"Camel",{n,n}},"Eulerian"],{n,20}]

Centipede

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

CocktailParty

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

Complete

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

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

seq=Table[GraphData[{"Complete",n},"Eulerian"],{n,30}]

Table[Piecewise[{{True,Mod[n,2]==1}},False],{n,30}]==seq

CompleteBipartite n×n

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

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

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

Table[Piecewise[{{True,Mod[n,2]==0}},False],{n,20}]==seq

CompleteBipartite m×n

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

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

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"CompleteBipartite",{m,n}},"Eulerian"],
Piecewise[{{True,Mod[m,2]==0&&Mod[n,2]==0}},False]
},{n,10},{m,n}],1],{_,x_,x_}]

CompleteTripartite n×n×n

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

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

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

CompleteTripartite k×m×n

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

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

DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"CompleteTripartite",{k,m,n}},"Eulerian"],
Piecewise[{{True,Equal@@Mod[{k,m,n},2]}},False]
},{n,10},{m,n},{k,m}],2],{_,x_,x_}]

Piecewise[{{True,Equal@@Mod[{k,m,n},2]}},False]

CrossedPrism

seq=Table[GraphData[{"CrossedPrism",2n},"Eulerian"],{n,2,12}]

Crown

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

CubeConnectedCycle

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

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

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

Cycle

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

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

seq=Table[GraphData[{"Cycle",n},"Eulerian"],{n,3,30}]

CycleComplement

seq=Table[GraphData[{"CycleComplement",n},"Eulerian"],{n,3,20}]

DiagonalIntersection

seq=Table[GraphData[{"DiagonalIntersection",n},"Eulerian"],{n,3,14}]

Dipyramid

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

DorogovtsevGoltsevMendes

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

DoubleCone

seq=Table[GraphData[{"DoubleCone",n},"Eulerian"],{n,3,20}]

Empty

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

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

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

FibonacciCube

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

Fiveleaper n×n

seq=Table[GraphData[{"Fiveleaper",{n,n}},"Eulerian"],{n,20}]

Flower

seq=Table[GraphData[{"Flower",n},"Eulerian"],{n,5,20}]

FoldedCube

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

Gear

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

Giraffe n×n

seq=Table[GraphData[{"Giraffe",{n,n}},"Eulerian"],{n,20}]

Goldberg

seq=Table[GraphData[{"Goldberg",n},"Eulerian"],{n,3,20}]

Grid n×n

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

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

seq=Table[GraphData[{"Grid",{n,n}},"Eulerian"],{n,20}]

Table[Piecewise[{{True,n==1||n==2}},False],{n,20}]==seq

Grid m×n

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

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

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Grid",{m,n}},"Eulerian"],
Piecewise[{{True,m ==n==1||m ==n==2}},False]
},{n,10},{m,n}],1],{_,x_,x_}]

Grid n×n×n

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

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

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

Table[Piecewise[{{True,n==1}},False],{n,10}]==seq

Grid k×m×n

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

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

DeleteCases[Sort@Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"Eulerian"],
Piecewise[{{True,k==m==n==1||(Min[k,m,n]==1&&Max[k,m,n]==2&&k m n==4)}},False]
},{n,5},{m,n},{k,m}],2],{_,x_,x_}]

HalvedCube

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

Hanoi

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

Helm

seq=Table[GraphData[{"Helm",n},"Eulerian"],{n,3,20}]

Hypercube

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

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

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

Table[Piecewise[{{True,Mod[n,2]==0}},False],{n,0,10}]==seq

Keller

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

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

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

Table[Piecewise[{{True,Mod[n,2]==1}},False],{n,5}]==seq

King n×n

seq=Table[GraphData[{"King",{n,n}},"Eulerian"],{n,20}]

Knight n×n

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

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

seq=Table[GraphData[{"Knight",{n,n}},"Eulerian"],{n,20}]

Table[Piecewise[{{True,n==1||n==2||n==3}},False],{n,20}]==seq

Knight m×n

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

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

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Knight",{m,n}},"Eulerian"],
Piecewise[{{True,Min[m,n]==1||m==n==2||m==n==3}},False]
},{n,10},{m,n}],1],{_,x_,x_}]

Ladder

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

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

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

Table[Piecewise[{{True,n==2}},False],{n,20}]==seq

LadderRung

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

LucasCube

seq=Table[GraphData[{"LucasCube",n},"Eulerian"],{n,15}]

MengerSponge

seq=Table[GraphData[{"MengerSponge",n},"Eulerian"],{n,3}]

MoebiusLadder

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

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

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

Mycielski

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

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

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

Table[Piecewise[{{True,n==1||n==3}},False],{n,11}]==seq

Odd

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

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

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

Table[Piecewise[{{True,Mod[n,2]==0||n==1}},False],{n,7}]==seq

Pan

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

Path

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

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

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

Table[Piecewise[{{True,n==1}},False],{n,20}]==seq

PathComplement

seq=Table[GraphData[{"PathComplement",n},"Eulerian"],{n,20}]

Pell

seq=Table[GraphData[{"Pell",n},"Eulerian"],{n,9}]

Prism

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

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

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

Queen n×n

seq=Table[GraphData[{"Queen",{n,n}},"Eulerian"],{n,20}]

Rook n×n

seq=Table[GraphData[{"Rook",{n,n}},"Eulerian"],{n,20}]

RookComplement n×n

seq=Table[GraphData[{"RookComplement",{n,n}},"Eulerian"],{n,20}]

SierpinskiCarpet

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

SierpinskiGasket

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

SierpinskiTetrahedron

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

Spoke n×n

seq=Table[GraphData[{"Spoke",{n,n}},"Eulerian"],{n,5}]

StackedBook

seq=Table[GraphData[{"StackedBook",{n,n}},"Eulerian"],{n,10}]

StackedPrism

seq=Table[GraphData[{"StackedPrism",{n,n}},"Eulerian"],{n,3,5}]

Star

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

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

seq=Table[GraphData[{"Star",n},"Eulerian"],{n,25}]

Table[Piecewise[{{True,n==1}},False],{n,25}]==seq

Sun

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

Sunlet

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

TorusGrid n×n

seq=Table[GraphData[{"TorusGrid",{n,n}},"Eulerian"],{n,3,20}]

Transposition

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

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

seq=Table[GraphData[{"Transposition",n},"Eulerian"],{n,6}]

Do[Print[{{"Transposition",n},EulerianGraphQ[TranspositionGraph[n]]//Timing,MaxMemoryUsed[]/10^.9}],{n,10}]

tf={True,False,False,True,True,False,False,True,True};

l=Boole[tf]

Table[Mod[1+Floor[n/2],2],{n,9}]==l

Table[Piecewise[{{True,Mod[1+Floor[n/2],2]==1}},False],{n,6}]==seq

Table[Piecewise[{{True,Mod[Floor[n/2],2]==0}},False],{n,6}]==seq

Trapezohedron

Entity["Graph",{"Trapezohedron",n}]["Eulerian"]

Entity["Graph",{"Trapezohedron",n}]["Noneulerian"]

seq=Table[GraphData[{"Trapezohedron",n},"Eulerian"],{n,3,20}]

Triangular

seq=Table[GraphData[{"Triangular",n},"Eulerian"],{n,2,20}]

TriangularGrid

seq=Table[GraphData[{"TriangularGrid",n},"Eulerian"],{n,0,20}]

TriangularHoneycombAcuteKnight

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

TriangularHoneycombBishop

seq=Table[GraphData[{"TriangularHoneycombBishop",n},"Eulerian"],{n,20}]

TriangularHoneycombObtuseKnight

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

TriangularHoneycombQueen

seq=Table[GraphData[{"TriangularHoneycombQueen",n},"Eulerian"],{n,20}]

TriangularHoneycombRook

seq=Table[GraphData[{"TriangularHoneycombRook",n},"Eulerian"],{n,20}]

TriangularSnake

seq=Table[GraphData[{"TriangularSnake",n},"Eulerian"],{n,1,20,2}]

Web

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

Wheel

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

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

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

WheelComplement

seq=Table[GraphData[{"WheelComplement",n},"Eulerian"],{n,4,20}]

WhiteBishop n×n

seq=Table[GraphData[{"WhiteBishop",{n,n}},"Eulerian"],{n,2,20}]

Zebra n×n

seq=Table[GraphData[{"Zebra",{n,n}},"Eulerian"],{n,20}]

Testing

Counts

Simple

A133736

1, 1, 2, 3, 7, 15, 52, 236, 2018, 33044, 1181670, 87720798,

Count[#,True]&/@Table[(EulerianGraphQ/@GraphData/@GraphData[n]),{n,7}]

Count[#,True]&/@Table[(EulerianGraphQ/@Graphs[n]),{n,8}]//Timing

Count[#,True]&/@Table[(EulerianGraphQ/@Graphs[n]),{n,9}]//Timing

Connected

A003049

1, 0, 1, 1, 4, 8, 37, 184, 1782, 31026, 1148626, 86539128,

Count[#,True]&/@Table[(EulerianGraphQ/@GraphData/@GraphData["Connected",n]),{n,7}]

Count[#,True]&/@Table[(EulerianGraphQ/@ConnectedGraphs[n]),{n,8}]//Timing

Count[#,True]&/@Table[(EulerianGraphQ/@ConnectedGraphs[n]),{n,9}]//Timing

Checks

<<MathWorld`Graphs`

DeleteCases[{#,EulerianGraphQ[GraphData[#]],MyEulerianGraphQ[GraphData[#]]}&/@GraphData["Connected",;;6],{_,x_,x_}]//Timing

DeleteCases[{#,EulerianGraphQ[GraphData[#]],GraphData[#,"Eulerian"]}&/@GraphData["Connected",;;6],{_,x_,x_}]//Timing