I Prove that in any simple graph with more than two vertices, two equal paths of maximal length must intersect

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.
 

StoneTemplePython

Science Advisor
Gold Member
1,056
503
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.
 
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."
 

StoneTemplePython

Science Advisor
Gold Member
1,056
503
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
 

berkeman

Mentor
54,966
5,194
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.
 

Want to reply to this thread?

"Prove that in any simple graph with more than two vertices, two equal paths of maximal length must intersect" You must log in or register to reply here.

Related Threads for: Prove that in any simple graph with more than two vertices, two equal paths of maximal length must intersect

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top