Let me now define a tree graph.

A tree is a connected graph without cycles.

There is an equivalent definition of a tree.

A tree is a connected graph on n vertices and n-1 edges.

Apparently these three definitions are equivalent,

moreover there is a third useful equivalent definition of a tree.

A tree is a graph where there is a unique path between every pair of vertices.

If there is only one simple path between every pair of vertices, this graph is a tree.

We'll later prove that these three definitions are equivalent,

but now we'll use them.

Here's an example of a tree.

How can we check that this is a tree?

Clearly this is a connected graph and there are no cycles.

You can check, you can not start with a vertex and get back to it by using distinct edges.

So that no cycles and its connected.

So what's the first definition of a tree, it is a tree.

There's a second definition which says that a tree is a connected graph

on n vertices and n-1 edges,

it is also tree because it has nine vertices and eight edges.

There's a connected graph with n equals nine vertices and n-1 equals eight edges.

And the third definition says that a tree has a unique simple path

between every pair of vertices.

We can check, for example I want to find a path from this vertex to this vertex.

You can check that there is only one path which goes like this.

Well say I want to go from this vertex to that vertex,

I'll take this edge, this edge, this edge, this edge and this edge.

You can check that for every pair of vertices there is only one path between them,

there's only one simple path.

This is why these graphs are called trees because they look like branches of a tree,

especially if you rotate them.

A path is always a tree because it's a connected graph without cycles or it is

a connected graph on n vertices with n-1 edges.

And it also looks like a tree if you rotate it.

Here is another tree, you can check it's a tree by any of these definitions.

You can always choose an arbitrary vertex of a tree and call it the root of this tree.

And now when you have a root, you can for example

draw a tree the same way that we saw on the previous slide.

You can draw the root somewhere on the top level

then on the second level draw all neighbors of the root,

all vertices which are on distance one from the root then

in the next level you draw all vertices which are in distance two from the root,

which are neighbors to the vertices on the first level.

This is one way to draw a graph or to draw a tree.

And here we have chosen some vertex which we'll call arrow

but you could have chosen any other vertex and draw it differently.

So this is this tree and here it's clear why a tree always has n-1 edges.

Because every vertex here has exactly one what we call parent,

it has exactly one vertex on that level right above it,

which is connected to it.

For example, V7 is connected to V9.

Every vertex has its parent except for the root.

Now I want you to remove the minimum number of edges from this graph,

such that there is a unique simple path between every pair of them.

Now we know that if a graph has a unique simple path between every pair of vertices,

then it is a tree.

And we also know that a tree is a connected graph on n vertices with n-1 edges.

So we can just remove edges from this graph until we are left with only four edges,

but we also have to keep it connected.

So for example, I can remove this edge V1, V2.

Now I can remove this edge V1, V3 then V1, V4.

Can I remove V1, V5?

No, I will loose connectivity, I cannot remove it.

Okay, I will remove this edge V2, V3 and then there is V2, V4 and then V3, V4.

We get a connected graph with five vertices and four edges.

So it's a tree, so there's a unique path between every pair of vertices

and that's easy to see.

If you want to go from V2 to V4, just go through V5.

If you want to go for V1 to V3, again, go through V5.