5 ms·

An unsolved problem in graph theory

79 points by prideout 7y ago

gweinberg 7y ago
Pretty cool. I would think there would either be an algorithm to label the vertices or an example of one that cannot be elegantly labelled, but I guess not. I's pretty obvious that node n must be adjacent to node 0, since that's the only way to get edge n. And it's pretty obvious that if you have one labeling you can get another by replacing m with n-m, so all the edges keep the same labels. But that's about as far as I get.
noud 7y ago
The definition of graceful graph is wrong. Edges E_{i,j} should have unique values as well, i.e. {E_{i,j}} = {1, 2, ..., n}. Otherwise it's trivial to label every graph into a graceful graph.
- Syzygies 7y ago
  Yes, thank you. I kept looking at the date, wondering if it was already April 1st, was this a brilliant troll? Then I checked Wikipedia.
- prideout 7y ago
  Good catch, the fix will show up soon.
empath75 7y ago
Numberphile video: https://www.youtube.com/watch?v=v5KWzOOhZrw https://www.youtube.com/watch?v=v5KWzOOhZrw
cschmidt 7y ago
A month ago [1] there was a post about the proof of Ringel’s conjecture, that a complete graph can be covered by certain trees. Sadly it was a non-constructive proof. In a little googling of the Graceful Tree Conjecture, it turns out that Ringel's conjecture inspired the Graceful Tree Conjecture [2] It was shown that the GTC implies Ringel's conjecture. Fun to see the connection in the last two math problems I dipped into. [1] https://news.ycombinator.com/item?id=22373701 https://news.ycombinator.com/item?id=22373701 [2] https://tspace.library.utoronto.ca/bitstream/1807/13623/1/MQ53395.pdf https://tspace.library.utoronto.ca/bitstream/1807/13623/1/MQ... page 13 in their numbering
- sdenton4 7y ago
  I, uh, wasted a bit of time once on the Tree Packing conjecture of Gyarfas: https://arxiv.org/abs/1104.0642 https://arxiv.org/abs/1104.0642 In your left hand, place a complete graph, which has n-choose-2 edges. In your right hand, a collection of trees on 2, 3, 4, ..., n-1 vertices, which, by miraculous concidence, also has n-choose-2 edges. Q: Can you pack the trees into a complete graph with no overlapping edges?
jjtheblunt 7y ago
little mistake: "Vi <> Vj for all i,j" fails if i == j, which isn't forbidden.
- prideout 7y ago
  Nice one! Fixing...

79 points by prideout 7y ago

Pretty cool. I would think there would either be an algorithm to label the vertices or an example of one that cannot be elegantly labelled, but I guess not. I's pretty obvious that node n must be adjacent to node 0, since that's the only way to get edge n. And it's pretty obvious that if you have one labeling you can get another by replacing m with n-m, so all the edges keep the same labels. But that's about as far as I get.

noud 7y ago

The definition of graceful graph is wrong. Edges E_{i,j} should have unique values as well, i.e. {E_{i,j}} = {1, 2, ..., n}. Otherwise it's trivial to label every graph into a graceful graph.

Syzygies 7y ago
Yes, thank you. I kept looking at the date, wondering if it was already April 1st, was this a brilliant troll? Then I checked Wikipedia.
prideout 7y ago
Good catch, the fix will show up soon.

empath75 7y ago

Numberphile video: https://www.youtube.com/watch?v=v5KWzOOhZrw https://www.youtube.com/watch?v=v5KWzOOhZrw

cschmidt 7y ago

A month ago [1] there was a post about the proof of Ringel’s conjecture, that a complete graph can be covered by certain trees. Sadly it was a non-constructive proof. In a little googling of the Graceful Tree Conjecture, it turns out that Ringel's conjecture inspired the Graceful Tree Conjecture [2] It was shown that the GTC implies Ringel's conjecture. Fun to see the connection in the last two math problems I dipped into. [1] https://news.ycombinator.com/item?id=22373701 https://news.ycombinator.com/item?id=22373701 [2] https://tspace.library.utoronto.ca/bitstream/1807/13623/1/MQ53395.pdf https://tspace.library.utoronto.ca/bitstream/1807/13623/1/MQ... page 13 in their numbering

sdenton4 7y ago
I, uh, wasted a bit of time once on the Tree Packing conjecture of Gyarfas: https://arxiv.org/abs/1104.0642 https://arxiv.org/abs/1104.0642 In your left hand, place a complete graph, which has n-choose-2 edges. In your right hand, a collection of trees on 2, 3, 4, ..., n-1 vertices, which, by miraculous concidence, also has n-choose-2 edges. Q: Can you pack the trees into a complete graph with no overlapping edges?

jjtheblunt 7y ago

little mistake: "Vi <> Vj for all i,j" fails if i == j, which isn't forbidden.

prideout 7y ago
Nice one! Fixing...