The discussion revolves around the problem of proving that in any simple graph with more than two vertices, two equal paths of maximal length must intersect. The focus includes the exploration of extremal arguments and the implications of path intersections in tree graphs.
Participants express some agreement on the need for paths to intersect in connected graphs, but there is uncertainty regarding the clarity of the problem statement and the specific details of the proof being sought.
The discussion highlights limitations in the initial problem statement and the need for clearer definitions, as well as the potential for misunderstanding the requirements of the proof.
What exactly are you trying to prove?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.
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 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.
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 connectedSuperyoshiom 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.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."