Proof: Necessary Component Condition for Hamiltonian Graphs | Graph Theory

Let G be a Hamiltonian graph. Then deleting any k vertices from G results in a graph with at most k components. We prove this necessary component condition for Hamiltonian graphs in today's video graph theory lesson!

Remember a Hamiltonian graph is a graph containing a Hamiltonian cycle - a cycle containing all vertices of the graph. We'll prove this necessary condition of Hamiltonian graphs using a similar result about graphs with Hamiltonian paths.

The result we use for this proof states that if G is a graph containing a Hamiltonian path and we delete any k vertices from G, then the resulting graph has at most k+1 components. We prove this result in this lesson:    • Proof: Necessary Component Condition ...  

Lesson on Hamiltonian Graphs:    • Hamiltonian Cycles, Graphs, and Paths...  
Proof of Ore's theorem for Hamilton graphs:    • Proof: Ore's Theorem for Hamiltonian ...  
Proof of Dirac's Theorem for Hamilton graphs:    • Proof: Dirac's Theorem for Hamiltonia...  



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