2
a/graphtheory posted by smh 3 weeks ago

https://www.sciencedirect.com/science/article/pii/S0166218X19301969

http://www.math.kit.edu/iag6/~axenovich/media/path-trans.pdf


Both papers proves that the conjecture holds with certain graphs. Are there more papers like these?

Log in or sign up to leave a comment     
Log in
Sign up
0
piaero · 3 weeks ago [-]

The second paper mentions that this holds in the case of two longest paths. What is the intuition behind this proof?

1
smh · 3 weeks ago [-]

If the two paths didn't share a vertex then you could construct a new path using the two longest paths (since the graph is connected) that is longer than the longest paths, resulting in a contradiction.