[ad_1]
Last time we showed the basic characteristics of wood; it is connected to a minimum and maximum serial port. We are now going to investigate the number of edges of the tree in relation to the number of vertices.
First, I want to show that every tree has “leaves.” A leaf is a vertex of degree 1. To do this, consider the longest path in the tree and mark vertices on this path 1, 2, …, k. Now vertex 1 is not able to connect to the 2, 3, …, k, as this would create a cycle. Vertex 1 is not able to connect with other vertex in the graph, it would be a longer path in the tree. The degree of this vertex will be 1. In fact, for the same reasons, vertex K also has a grade 1.
This little result is very useful when it comes to theorizing about the tree. It is useful for a wonderful mathematical tool that is stimulated. I’ll give you an example.
I’ll show a tree with n vertices has n-1 edges. We shall do this by induction. Consider Singleton graph at one vertex; This has no edges and one vertex. Now consider the graph of n vertices. Pick a leaf on this graph and remove it. Now you have a graph on n-1 vertices exposed to n-2 edges with the induction hypothesis. But you have only removed one edge of the original graph, which must have had n-1 edges.
Now we have shown that trees with n vertices will have N-1 edges.
[ad_2]