Graphs Have at Least n-m Components | Graph Theory

A graph with n vertices and m edges has at least n-m components. We justify this claim in today's graph theory lesson. Imagine a graph with its n vertices and without any edges. This graph would have n components, each vertex is a trivial subgraph. Then, each additional edge could join at most two components, thus reducing the number of components by 1 at most. Hence, with m edges, the graph must have at least n-m components. #GraphTheory

What is a Component of a Graph?    • What is a Component of a Graph? | Con...  

Graph Theory playlist:    • Graph Theory  
Graph Theory exercises:    • Graph Theory Exercises  

◉Textbooks I Like◉
Graph Theory: https://amzn.to/3JHQtZj
Real Analysis: https://amzn.to/3CMdgjI
Proofs and Set Theory: https://amzn.to/367VBXP (available for free online)
Statistics: https://amzn.to/3tsaEER
Abstract Algebra: https://amzn.to/3IjoZaO
Discrete Math: https://amzn.to/3qfhoUn
Number Theory: https://amzn.to/3JqpOQd

★DONATE★
◆ Support Wrath of Math on Patreon for early access to new videos and other exclusive benefits:   / wrathofmathlessons  
◆ Donate on PayPal: https://www.paypal.me/wrathofmath

Thanks to Petar, dric, Rolf Waefler, Robert Rennie, Barbara Sharrock, Joshua Gray, Karl Kristiansen, Katy, Mohamad Nossier, and Shadow Master for their generous support on Patreon!

Thanks to Crayon Angel, my favorite musician in the world, who upon my request gave me permission to use his music in my math lessons: https://crayonangel.bandcamp.com/

Follow Wrath of Math on...
● Instagram:   / wrathofmathedu  
● Facebook:   / wrathofmath  
● Twitter:   / wrathofmathedu  

My Math Rap channel:    / @mathbars2020