An unsolved problem in graph theory | Hacker News Reader

An unsolved problem in graph theory

prideout.net

79 pointsprideout9 comments

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.

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.

Good catch, the fix will show up soon.

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

[2] https://tspace.library.utoronto.ca/bitstream/1807/13623/1/MQ... page 13 in their numbering

I, uh, wasted a bit of time once on the Tree Packing conjecture of Gyarfas: 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?

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.

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

little mistake:

   "Vi <> Vj for all i,j"

fails if i == j, which isn't forbidden.

Nice one! Fixing...

Reply on news.ycombinator.com