Copyright | Copyright (C) 2021 Yoo Chung |
---|---|

License | GPL-3.0-or-later |

Maintainer | dev@chungyc.org |

Safe Haskell | Safe-Inferred |

Language | GHC2021 |

Part of Ninety-Nine Haskell Problems. Some solutions are in Solutions.P92.

# Documentation

gracefulTree :: G -> Maybe (Map Vertex Int) Source #

It has been conjectured that if graph \(G=(V,E)\) is a tree with \(n\) vertexes,
which necessarily means that it has \(n-1\) edges, then there is
a *graceful labeling* of the tree.
This means that there is a way to label each vertex with integers from 1 to \(n\)
such that for every integer \(m\) from 1 to \(n-1\), there is an edge whose difference
in vertex labels is \(m\). I.e., there is a bijection \(l : V \rightarrow \{ k \,|\, 1 \leq k \leq n \}\)
such that \(\{ |l(v)-l(v')| \,|\, \{v,v'\} \in E \} = \{ k \,|\, 1 \leq k \leq n-1 \}\).
There is no known counterexample, but neither is it proven that this is true for all trees.

For example, the following is a graceful labeling of the tree graph `tree92`

:

Write a function which will gracefully label a tree graph.
If there is no graceful labeling for a particular tree,
return `Nothing`

, and write up the counterexample for publication.

### Examples

`>>>`

Just (fromList [(1,5),(2,2),(3,1),(4,7),(5,3),(6,6),(7,4)])`gracefulTree tree92`

`>>>`

Just (fromList [(1,1),(2,10),(3,7),(4,3),(5,5),(6,6),(7,14),(8,13),(9,12),...`gracefulTree tree92'`

### Notes

Problem 92 in the original list referred to this conjecture as "Von Koch's conjecture". However, I could not find any reference confirming that von Koch actually made this conjecture. From the style the problem was written in, it seems likely this was an imaginary scenario to make the problem feel more personal and fun, rather than something which actually happened.

It is too unbelievable for me to have met the mathematician in question, so this was rewritten to a more dry presentation.

Tree graph used for the example in `gracefulTree`

.

A 14-vertex tree graph to try `gracefulTree`

on.