Proof: Forest Graphs have n-k Edges | Graph Theory

A forest of order n with k components has size n-k. This is a generalization of the result that tree graphs with n vertices have n-1 edges. We prove this generalization in today's graph theory lesson!

A forest is an acyclic graph. It is like a tree graph except it does not need to be connected, thus its components are trees.

We rely on the obvious fact that the order of a graph is the sum of the orders of its components (recall that the order of a graph is the number of vertices it has), similarly the size of a graph (its number of edges) is the sum of the sizes of its components. We also use the result that a tree of order n has size n-1.

Proof of the size of a tree:    • Proof: Tree Graph of Order n Has Size...  

◆ Donate on PayPal: https://www.paypal.me/wrathofmath
◆ Support Wrath of Math on Patreon:   / wrathofmathlessons  

I hope you find this video helpful, and be sure to ask any questions down in the comments!
+WRATH OF MATH+

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

My Music Channel:    / seanemusic