Log in or sign up to leave a comment     
Log in
Sign up
1
piaero · 5 months ago [-]

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

2
smh · 5 months 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.