Euler Graph

Author

Eric W. Weisstein
February 5, 2010

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

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

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

Code

EulerQ[g_Graph]:=And@@EvenQ/@Degrees[g]
EulerQ[g_System`Graph]:=And@@EvenQ/@VertexDegree[g]

A bit slower actually:

EulerQ[g_Graph]:=If[V[g]==1,True,EvenQ/@(And@@Degrees[g])]

Counts

Graphs/@Range[9];
ConnectedGraphs/@Range[9];

All

Count[#,_?EulerQ]&/@Graphs/@Range[8]//Timing

Count[#,_?EulerQ]&/@Graphs/@Range[9]//Timing

Connected == Eulerian Graphs

Count[#,_?EulerQ]&/@ConnectedGraphs/@Range[8]//Timing

Count[#,_?EulerQ]&/@ConnectedGraphs/@Range[8]//Timing

Count[#,_?EulerQ]&/@ConnectedGraphs/@Range[9]//Timing

Euler but not Eulerian

Length/@Table[Select[GraphData[n],GraphData[#,"Eulerian"]&],{n,6}]

Length/@Table[Select[GraphData[n],EulerQ[Graph[#]]&],{n,6}]

?Graphs

Options[Graphs]

Graphs[2,"Format"->"V7"]

Length/@(gs=Table[Select[Graphs[n],!EulerianGraphQ[#]&&EulerQ[#]&],{n,8}])

gs2=DeleteCases[Map[RecognizeGraph,gs,{2}],{}]

GraphicsGrid[Map[GraphPlot[GetGraph[#]]&,gs2,{2}],Dividers->All,ImageSize->400]

http://oeis.org/A002854

euler={1,1,2,3,7,16,54,243,2038,33120,1182004,87723296,12886193064,3633057074584,1944000150734320,1967881448329407496,3768516017219786199856,13670271807937483065795200};

http://oeis.org/A133736

eulerian={1,1,2,3,7,15,52,236,2018,33044,1181670,87720798,12886156666,3633055848955,1944000061673516,1967881435350411681,3768516013573481061951,13670271805989797561408684};

euler-eulerian

Images

gs=Map[GraphData[RecognizeGraph[#]]&,DeleteCases[Select[#,EulerQ]&/@Graphs/@Range[6],{}],{2}];

GraphicsGrid[Flatten[Partition[#,10,10,{1,1},{}]&/@gs,1],ImageSize->400,Spacings->50,Dividers->All]