Size of Tree Graph Complement equals Size of a Complete Graph | Graph Theory

Описание: How many edges does the complement of a tree graph have? We'll be answering this question in today's graph theory video lesson using the fact that a tree of order n has n-1 edges, that is - a size of n-1. Knowing this, we can easily find an expression for the size of the complement of a tree graph, by subtracting (n-1) from the total number of possible edges on n vertices. Then, we will show this is actually the same as the size of a complete graph on n-1 vertices.

Lesson on trees:    • Intro to Tree Graphs | Trees in Graph Theo...  
Proof a tree graph of order n has size n-1:    • Proof: Tree Graph of Order n Has Size n-1 ...  

The converse of the order n size n-1 statement is also true, almost. That is - if a connected graph has one less edge than vertices, then it must be a tree (a connected acyclic graph). Here is a proof:    • Proof: Graph with n Vertices and n-1 Edges...  

I didn't realize I already did a video on almost exactly this topic, where I just go over what the size of the complement of a tree graph is, without comparing it to a complete graph. Here is that lesson if you want to hear me run through the same explanation again:    • Size of the Complement of a Tree Graph | G...  

◆ 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