Proof: Two Longest Paths Have a Common Vertex | Graph Theory, Connected Graphs
ฝัง
- เผยแพร่เมื่อ 1 ส.ค. 2024
- In any connected graph, two longest paths will always have a common vertex! We'll prove this theorem in today's video graph theory lesson using contradiction!
We suppose we have two longest paths in a connected graph that do NOT have a common vertex, and we'll be able to find a longer path, producing a contradiction!
I hope you find this video helpful, and be sure to ask any questions down in the comments!
+WRATH OF MATH+
◆ Support Wrath of Math on Patreon: / wrathofmathlessons
Follow Wrath of Math on...
● Instagram: / wrathofmathedu
● Facebook: / wrathofmath
● Twitter: / wrathofmathedu
My Music Channel: / seanemusic
Using that last vertex of p and first vertex of q belonging to the path x from P to Q was EXACTLY the little push I needed to finish the demo and you explained it so simply! Thank you!
Two longest paths? More like "Terrific playlist, with educational value that's unmatched!" 👍
Very helpful! Thanks! From South Africa!
You're very welcome, David! Thanks for watching!
Dude you are a cool teacher ❤
I do my best - thanks for watching!
Thank you so much sir
My pleasure - thanks for watching!
thank you
My pleasure, thanks for watching!
Could someone explain why can we assume that P and Q are equal in length?
If P is longer than Q (or vice versa), then Q isn't a longest path.
@@WrathofMath of course, thanks for the reply
SUBBED.
Thank you!
if G is a simple graph with d(v) ≥ k, ∀v ∈ v(G), then G contains a path of length at least k. if k ≥ 2, then g contains a cycle of length k +1.
Can you explain this barbarity please?
Very helpful! Thanks !
Why in the case of a directed graph weakly connected the two longest paths DONT have a common vertex ?
Glad it was helpful! And that's a great question, I don't remember if I mentioned directed graphs in the lesson but I don't think I had really thought of how this result does/doesn't apply to them.
We know immediately that our proof wouldn't work as is for directed graphs, since we discussed traveling in two different directions on a path - which may not be possible in a directed path unless all the edges involved have a similar edge in the opposite direction.
We then might seek to find a counter example to the result for directed graphs - my first thought, since we're discussing paths, was to consider a path graph. Imagine an undirected path graph, where we can describe the graph as the path (a, b, c, d). So for our example the path has 4 vertices. Now imagine we orient this graph by assigning one direction to each edge, such that vertices alternate having 0 in degree, 0 out degree, 0 indegree, and so on if you wanted to use a longer path graph.
By this, I mean that we orient the edges in this way: ab becomes (a, b); bc becomes (c, b); and cd becomes (c, d). Then, a has 0 in degree, b has 0 out degree, c has 0 indegree, and d has 0 out degree. Then, the longest directed paths in this graph all have length 1. We can go from a to b for a path of length 1, but since b has 0 out degree we know we cannot extend the path further. Similarly for the paths (c, b) and (c, d). In this case we can point out that (a, b) and (c, d) are both longest directed paths in the graph, and they do not share a common vertex.
Hope that helps! And if you didn't follow my explanation, try drawing it out!
@@WrathofMath Thank you very much for the detailed answer ! It helped me a lot !
Wowww ❤️
Anybody knows proof for 3 longest paths in conected graph have common vertex?
The proof should be pretty much the same. Considering you got 3 paths of the same length, you just do it for any 2 of them and according to the proof in the video you get path X which is longer than any of the 3 longest paths previously mentioned. Therefore it also contradicts the 3rd path being the longest.