Proof: Tree Graph of Order n Has Size n-1 | Graph Theory

A tree graph of order n has size n-1, any tree graph with n vertices has n-1 edges. Or stated a third way, tree graphs have one less edge than vertices. We prove this graph theory result in today's lesson!

One fact stated in this proof I assume we're comfortable with at this point is that a graph cannot be disconnected by deleting a vertex of degree 1. Here is some supplementary explanation of that fact. Let w be a vertex of degree 1 in a connected graph G. Any pair of vertices, u and v, in G, must be connected by a path P. If neither u nor v is equal to w then P cannot contain w, since if the path arrives at w it cannot leave w because w has degree 1 (it is only incident to one edge) and we know the path doesn't begin or end at w since neither u nor v is equal to w. So all of these paths connecting pairs of vertices exist in G-w. Thus, deleting an end vertex from G does not disconnect it.

Lesson on the converse of this statement:    • Proof: Graph with n Vertices and n-1 ...  

Proof that nontrivial tree graphs have at least two end vertices:    • Proof: Tree Graphs Have at Least Two ...  

Lesson on tree graphs:    • Intro to Tree Graphs | Trees in Graph...  



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

********************************************************************
The outro music is by a favorite musician of mine named Vallow, who, upon my request, kindly gave me permission to use his music in my outros. I usually put my own music in the outros, but I love Vallow's music, and wanted to share it with those of you watching. Please check out all of his wonderful work.

Vallow Bandcamp: https://vallow.bandcamp.com/
Vallow Spotify: https://open.spotify.com/artist/0fRtu...
Vallow SoundCloud:   / benwatts-3  
********************************************************************

+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