Solve three different, though equivalent definitions of trees. First, we'll say that a graph is a tree if it is a connected graph without cycles. But also say that a graph is a tree if it is a connected graph on n vertices and n- 1 edges. And our third definition says that a tree is a graph where there exists a unique simple path between every pair of vertices. Here's an example of a tree. It's quite easy to see that this graph is connected and doesn't have any cycles. So it is a tree according to the first definition. Also, this is a connected graph on nine vertices and eight edges, which means it is a tree according to the second definition as well. And for the third definition, we want to show that there exists a unique simple path between every pair of vertices. I want to show you, for every pair of vertices, I'll show you for one pair. For example, you want to find a path between these two vertices. So there's only one path between them, and it looks like this. And you can check if there is a unique simple path between every pair of vertices. Now let's prove that these three definitions are actually equivalent. How do we prove such a statement? One way to do it is to prove that the first definition implies the second one, the second definition implies the third one, and then we'll show that the third one implies the first one. This way I will prove that all three definitions I agree with. Why is that? Because, if for example, we want to say that the second definition is equivalent to the third one. We'll say the second one implies the third one, while the third one implies the first one, which in turn implies the second one. So the second definition implies the third one and the third one implies the second one, which means they're equivalent. All we need to show are these three implications. Let's start with the first one. If we have a connected graph without cycles on n vertices, then it must have exactly n- 1 edges. We can prove it by induction on n, the number of vertices in the graph. When n is 1, graph has 0 edges, which is exactly n- 1. Induction hypothesis says that, say we prove the statement for all graphs with the most k vertices. And in the induction step, we want to prove the statement for all graphs on k + 1 vertices. Here's how we do it. That was our graph without cycles and remove some edge, for example, this orange one. I want to say that we have now two connected components. First of all, why don't I have just one connected component? Because if this new graph is connected, say this vertex is connected to this one, then in the original graph, when I have this edge, I did have a cycle. Here it is. But I know that I started with a graph without cycles, a contradiction. Thus, I have at least two connected components. And actually I have at most two connected components. Because if I add this edge back, I can only decrease the number of connected components by one. So I have exactly two connected components, and none of them has cycles, because my original graph didn't have any cycles. All right, so I remove an edge. I have two smaller graphs connected in result cycles. Since they are smaller, I cannot apply induction hypothesis to that. If one of them has n1 vertices, the other one has n2 vertices, then I know that the first one, by induction hypothesis, has exactly n1- 1 edges. And the second has exactly n2- 1 edges. So my original graph has (n1- 1) + (n2- 1) + 1 removed edge, which is exactly n- 1 edges, the statement that we wanted to prove. So we'll prove the first implication. We'll prove that the first definition implies the second one. Let's prove that the second definition implies the third one. I want to say that if we kind of connect the graph on n vertices and n- 1 edges, then there exists a unique simple pattern between any pair of vertices. First of all, it's clear as if there exists at least one path because the graph is connected. Assume there are two paths between a pair of vertices. Then these two paths together give me a cycle. If I have a cycle, then I want to say that I have too many edges. Assume I have a cycle on m vertices and then m edges. I will be recovering all the edges of my original graph one by one. I know that my original graph is connected. So in order to connect to the cycle each vertex, I have to add at least one edge for each vertex. I have n- m remaining vertices. So I have to add at least n- 1 edges, which gives me the total number of at least n edges. But I assume that I start with a graph with m- 1 edges. This way, we get a contradiction. Here's how it works on our example. Assume I have two paths between a pair of vertices. For example, this one and this one. Here's the first path. And here is the second path. From these two paths, I can always extract a cycle, this yellow one. And now, I want to recover edges of my original graph. I will start with the six edges of the cycle, and then I want to add edges to the three remaining vertices. In order to connect each of them, I have to add at least one edge, which means I have at least nine edges on my graph with nine vertices. This is the meaning, I assumed my graph has m- 1 edges with n vertices. This way, we get a contradiction here. So we just proved that the first two implications. And the third one is actually trivial. We want to say that if there is a unique path between every pair of vertices, then there are no cycles. Indeed, I assume there exists a cycle in my graph. Then the first and the last vertices on this cycle have two single paths between them. Here is one red path, and here is the other yellow path. So we proved the third implication as well, which means we've finished the proof of the equivalence of these three definitions of trees.
