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

#### Superyoshiom

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

Gold Member
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.

#### Superyoshiom

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

Gold Member
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
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"

### 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