Find Two Equal Length Paths in a Tree Graph

Join the discussion
Ask a follow-up here, or get your own question answered by working scientists, mathematicians and engineers — people, not an autocomplete.
Real named experts · corrections over time · the nuance an AI answer skips
Sign up Log in
4 replies · 2K views
Superyoshiom
Messages
29
Reaction score
0
In order to try and sovle this problem, my idea here was to use an extremal argument, with two equal length maximum paths on a tree. I said that no matter where the two graphs started, they'd end up having to cross paths since if there were two distinct paths with equal lengths the graph would no longer be connected; the paths still needed to intersect.
 
Mathematics news on Phys.org
Superyoshiom said:
In order to try and sovle this problem, my idea here was to use an extremal argument, with two equal length maximum paths on a tree. I said that no matter where the two graphs started, they'd end up having to cross paths since if there were two distinct paths with equal lengths the graph would no longer be connected; the paths still needed to intersect.
What exactly are you trying to prove?

The title says "Prove that in any simple graph with more than two vertices, two equal"
which is a fragment that doesn't state the full problem... I don't see the problem stated in the body here either.
 
StoneTemplePython said:
What exactly are you trying to prove?

The title says "Prove that in any simple graph with more than two vertices, two equal"
which is a fragment that doesn't state the full problem... I don't see the problem stated in the body here either.
I'm sorry, the title cut off for some reason, it should say: "Prove that in any simple graph with more than two vertices, two equal paths of maximal length must intersect."
 
Superyoshiom said:
I'm sorry, the title cut off for some reason, it should say: "Prove that in any simple graph with more than two vertices, two equal paths of maximal length must intersect."
Got it. This was, basically, a homework problem in the calculus forums last week. And your sketch is right -- either there are common vertices in these maximal length paths or the graph isn't connected
 
Superyoshiom said:
I'm sorry, the title cut off for some reason, it should say: "Prove that in any simple graph with more than two vertices, two equal paths of maximal length must intersect."
I've updated your thread title for you.