Proof on Cut Vertices Incident with Bridges | Graph Theory

Let v be a vertex incident with a bridge of a graph G. Then v is a cut vertex of G if and only if the degree of v is greater than or equal to 2. We will prove this characterization of cut vertices incident with bridges in today's video graph theory lesson!

Lesson on cut vertices:    • What is a Cut Vertex? | Graph Theory,...  
Lesson on bridges:    • What are Bridges of Graphs? | Graph T...  

We will need the theorem that an edge of a graph is a bridge if and only if the edge lies on no cycles, here is a proof:    • Proof: An Edge is a Bridge iff it Lie...  

First we show that if v is a cut vertex then the degree of v is greater than or equal to 2. We do this by proving the contrapositive. Then, using proof by contradiction, we show that if the degree of v is greater than or equal to 2, then v is a cut vertex.



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