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.

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.

********************************************************************

+WRATH OF MATH+

Follow Wrath of Math on...

[oomfiekat]

Thanks for making videos. Your lessons always seem to help and are super clear to understand. A very underated channel since you always have brilliant delivery. :))

[advaithkumar]

Does this work?
Proceeding by induction( base case is the same as in video), assume that tree of order k has size k-1
Now consider constructing graph of order k+1
we take the graph with k vertices that is a tree and then add a disconnected vertex v_k+1 to it.
To ensure graph is connected now, add one edge to any of the other k vertices in the tree.
Adding another edge, however causes a contradiction since this would mean that the connected graph of order k+1 will have a cycle.
Hence the number of edges for the graph of order k+1 is (k-1) + 1 = k.

I think the argument is simliar to yours but mine takes an 'adding vertices' approach instead of deleting them.

[akshaytechtalks]

Thanks for adding related videos in the description. You made it really easy. Thanks Again.

[coca]

Can't believe this awesome video doesn't have a lot like

[PunmasterSTP]

n-1? More like "Nice videos, and learning is fun!" 👍

[saiyampramod]

Thank you so much for this video ! brilliant delivery

[ViolaTheSinger]

If we add a leaf to a tree, is it still a tree? so could we also use mathematical induction to prove that k+1 is true and just assuming that k is true

[teketselmengistu]

Show that an n-vertex graph G is a tree if and only if G has no cycle and
has n − 1 edges.

[spacepacehut]

Thanks for these proofs like there aren't any other materials out there I found till now that explains these so clearly..

[souvikkumarchandra]

Thank you sir.... love and many respect from india...

[thapakaji]

Yes, the converse of this statement is also true. This can be shown by considering spanning tree inside the connected graph.

[mvarchanathulasi]

Hello sir, I want to solve this problem could u please help me..
Show that if e (E ) then w(G) <=w(G - e) <=w(G)+ 1.

[mangubatdarwin]

How to prove that the converse of this theorem is not true?