Proof of a Characterization of Cut Vertices | Graph Theory

A vertex v, of a connected graph G, is a cut vertex if and only if there exist two vertices u and w - distinct from v - such that every u-w path in G contains v. We'll be proving this characterization of cut vertices in today's video graph theory lesson!
First we show that if v is a cut vertex of G, then there exist vertices u and w, distinct from v, such that v lies on every u-w path in G. If you want to see more about this direction of the proof - which is fairly straightforward - I go over a theorem which is very similar in this lesson: • Important Theorem abou...
The second direction is to assume that v is a vertex of G that lies on every u-w path for two vertices u and w, neither equal to v in G. Then we show v must be a cut vertex of G by analyzing the graph G-v, which clearly cannot have a u-w path. Thus G-v must be disconnected, so v is a cut vertex.
Lesson cut vertices: • What is a Cut Vertex? ...
Proof on cut vertices incident with bridges: • Proof on Cut Vertices ...
Proof connected graph contains two non-cut vertices: • Proof: Connected Graph...
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

[@LearningCS-jp4cb]

Could you also explain algorithm to find out cutvetex and bridges in a graph? Thanks

[@rafiqulislam1085]

could you make video to proof menger's and whitney's theorem and Tree characterizations theorem.

[@WrathofMath]

Thanks for watching and absolutely, great ideas! I'll get to them as soon as I can, I have been meaning to do Menger's Theorem for a while actually. By tree characterizations theorem do you mean theorems like:
A graph is a tree if and only if every two unique vertices are connected by a unique path.
A connected graph is a tree if and only if every edge of the graph is a bridge.
A connected graph of order n is a tree if and only if it has n-1 edges.

[@rafiqulislam1085]

@@WrathofMath yeah

[@saifalisaif8144]

please can you help me by how i can find cut vertex by DFS algorithm?

[@PunmasterSTP]

Characterization of cut? More like "Cool videos that can help get you out of a rut!" 👍