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."
A tree graph is a type of graph that consists of nodes connected by edges, with the following properties: 1) there is only one path between any two nodes, 2) there are no cycles or loops, and 3) there is a designated root node from which all other nodes can be reached. A tree graph is often used to represent hierarchical data structures.
Finding two equal length paths in a tree graph can be useful in various applications, such as network routing, data compression, and data analysis. It can help in identifying symmetrical patterns or structures within the data, and can also provide insights into the overall structure of the graph.
There are several approaches to finding two equal length paths in a tree graph. One method is to use a depth-first search algorithm to traverse the graph and compare the lengths of all possible paths. Another approach is to use dynamic programming techniques, where the lengths of all possible paths are stored in a table and compared to find the equal length paths.
Yes, it is possible to have more than two equal length paths in a tree graph. This can occur when there are multiple nodes with the same value or when there are multiple paths of the same length between two nodes. In such cases, all equal length paths can be identified using the same approach as finding two equal length paths.
One limitation of finding two equal length paths in a tree graph is that it can be computationally expensive for large graphs. As the number of nodes and edges in the graph increases, the time and memory required to find equal length paths also increases. Additionally, the presence of cycles or loops in the graph can make it more challenging to find equal length paths.