Graceful Tree Theorem

Author

Eric W. Weisstein
December 15, 2024

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

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

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

Maximally graceful graphs

Knuth (2024)

Anick (2016)

RecognizeGraph[Graph6A=EdgeAdd[PathGraph[Range@6,VertexLabels->Automatic],4\[UndirectedEdge]7]]

GraphData[{"Tree",{7,7}},"GracefulLabelingCount"]

TextGrid[MapIndexed[Prepend[#,#2[[1]]]&,{#[[1,1]],Rest/@#}&/@Table[SplitBy[SortBy[GraphData[#,{"GracefulLabelingCount","#","Graph"}]&/@GraphData["Tree",n],First],First][[-1]],{n,12}]],Dividers->All]

17 nodes / 16 edges

Anick (2016)

Knuth (2024, Fig. 42)

v={{549,77},{496,121},{514,16},{450,66},{384,102},{320,137},{253,137},{166,103},{80,136},{99,66},{34,102},{405,59},{341,24},{275,67},{212,15},{145,50},{80,15}};
g=ScaleGraph@Graph[Range@Length@v,UndirectedEdge@@@{e[11,10,8,9],e[17,16,15,14],e[8,14,7],e[6,5,4,3],e[4,2,1],e[5,14,13,12]},VertexCoordinates->v,VertexLabels->Automatic]

Through[{VertexCount,EdgeCount}[g]]

RecognizeGraph[g]

Graph[EdgeList[g]]

Special trees

GraphData["Tree",17]

Knuth (2024, Fig. 41)

v={#,#2-1}&@@@Join[Subdivide[{0,0},{2,1},2],Rest@Subdivide[{2,1},{0,2},2],Sequence@@Table[{i,j},{i,3,6},{j,{0,2}}],{{3,1},{8,0},{8,2},{8,1}}];
g=Graph[Range@Length@v,UndirectedEdge@@@{e[1,2,3,4,5],e[7,14,6],e[9,14,8],e[11,14,10],e[13,14,12],e[16,14,15],{14,17},{3,14}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

FindGracefulLabeling@g

Anick (2016), Fig. 6