Proof: Necessary Component Condition for Graphs with Hamiltonian Paths | Graph Theory

Let G be a graph with a Hamiltonian path (a path containing all vertices of the graph). Then, if we delete any k vertices of G, the resulting graph will have at most k+1 components. We prove this result in today's video graph theory lesson!

This is a fairly straightforward proof by induction. That said, explaining it is a little tricky; hence the length of this lesson. This result can be proven much more quickly like this...

First, prove the result for path graphs using induction. All graphs with Hamilton paths can be described as path graphs with more edges added. Certainly adding more edges will not INCREASE the number of components, and so the result holds for all graphs with Hamiltonian paths as well. I like the proof we do in this lesson, though it is far less elegant, because we are talking about the entire class of graphs with Hamiltonian paths from beginning to end, we don't narrow it down to only path graphs, and then extend the result. Additionally if nothing else, if it takes a bit more mental exercise to follow the more complicated proof - that's not all bad!

Here is a lesson talking about Hamiltonian paths and graphs if you need a recap:    • Hamiltonian Cycles, Graphs, and Paths...  



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