After we’ve seen in the last post an elegant example for using graph to solve a problem, it’s now time to proceed and meet some more definitions.

In math, when we are dealing with a structure, we usually like to define a sub-structure, examples for that are: sub-set, sub-group, sub-vector space and so on. The same thing applies to graphs as well, so let’s do it:

## Sub-Graphs

Let be a graph. We say that is a **sub-graph** of if:

In simpler words, A subgraph is just a graph which is made from vertices and edges from . We denote it by .

Here the higher graph is indeed a sub-graph, however, the bottom graph is **not** a sub-graph, since we’ve ‘added’ an extra edge.

A sub graph is said to be a **spanning sub-graph**, if . This is just a sub-graph that has all the vertices of the original graph. The sub graph in the above is not a spanning sub-graph, since it contains only 3 verticesf rom the original graph, and not all of them.

That’s an example of a **spanning sub-graph**, it is indeed a sub-graph that contains all of the original graph’s vertices.

Finally, for a set of vertices we will denote by the **spanned sub-graph** on which is defined as the sub-graph with as it’s set of vertices, and the edges of it, will be all the edges between vertices in that exists in . Formally:

G[U]=(U,\{e\in E:e\subseteq U\})

That’s an example for a spanned subgraph on the set of the marked vertices.

After wev’e seen all those defintions, right now I won’t prove anything related to them, however, they will play an important role in the future.

## Forest & Trees – The graphs

A graph is called a **Forset** if it has no cycle. If it is also connected, then it is called a **Tree**.

What? why would you call it like that? let’s see some visual examples of trees first:

I think that kinds of explains itself… those graph look like umm… trees, I am not talking about trees in a park or something like that (although it looks like roots of those trees) I am talking about family trees and stuff like that. If we consider all those trees a single graph, we get a graph which is not connected, and we called it a **forest**. Thus, a forest is just a** bunch of trees**, that is actually makes sense.

if is a forest, then a vertex with degree 1 is called a **leaf**, that’s also pretty intuitive, considering the forest in the above.

We are now ready to prove a lemma: If is a tree with two or more vertices, then it has at least two leaves. Let’s prove it:

First off all, since has at least two vertices, and it is connected as a tree, there must be an edge in it. We are now going to take the longest path in , which we will denote by (such a path exits since the graph is **finite** – the number of vertices is finite).

Now, I want you to notice this fact: every edge that is incident to has to ‘go back’ to the longest path, i.e. it’s second endpoint is in the set . Why, because if it woudn’t go back to the path, we will get a longer path, which contradicts being the longest path.

So we understand that if there is such an edge, it must ‘come back’ to the path. However, if there was an edge other than we would have get a **cycle** in the graph which is a contradiction for being a tree!

Thus, is incident to only one edge: , then and we found a leaf! The same process applies to as well, and we have found two leaves, as required.

Cool, notice that this proof actually gives us some sort of an algorithm to find leaves in a tree – we find the longest path in the tree and take the path’s endpoints. This algorithm is not really efficient, but it is something though…

I want to prove another lemma, which says that if we remove a leaf from a tree with at least two vertices, the sub-graph that we will get, is also a tree.

We denote by the graph spanned by the original set of vertices minus the removed leaf – , where .

- has no cycles, since has no cycles.
- is connected: Let . There is a path between in . This path also appears in since it is not possible that is ‘goes through’ the leaf, why? since if it went through the leaf, then the degree of the lead had to be at least 2, which is impossible since it is a leaf.

We have showed that has no cycles and is connected, thus is a tree!

To end this post, I would like to present 3 equivalent definitions for a tree, and prove that they are indeed equivalent.

Suppose is a graph with vertices, the following are equiavilent:

- is a tree (connected with no cycles).
- is connected and .
- has no cycles and .

The proofs are really simple and elegant, I really like them, so I shall begin so you will like them too

Let’s start with . We need to show that a tree has edges. I am going to prove it by induction.

When the graph is just a single vertex, thus, there are no edges at all, then .

For some general , we will pick a leaf and remove it. By doing so, we get a new graph – , we have proved before that is also a tree, while it also has vertices. by induction, we know that . Now, since is a leaf, it is incident to only one edge, thus, when removing we only ‘lose’ one edge. Therefore, as required.

Now, let’s prove . Suppose that is connected with edges, we need to show that it has no cycles.

We will remove one edge from each cycle (think why the graph remains connected) until we get a graph with no cycles. is a tree with vertices, we just proved that . However, as well, thus, we haven’t removed any edge from the graph, therefore, it has no cycles!

Now for the last part, we will show that . has no cycles and edges. We need to show that it is connected.

Denote by the componets of . Each components is a tree (since it is connected, and the has no cycles) which is **spanned **by . In other words, is a tree. Thus: . Overall, the number of edges in is the sum of the number of edges from each component:

e(G)=\sum_{i=1}^ke(V[C_i])=\sum_{i=1}^k(|V(C_i)| - 1)=\sum_{i=1}^k|V(C_i)| - k=n-k

On the other hand, we know that , thus and we get that . This means that there is only one component, therefore, the graph is connected.

## Summary

In this post we made some progress: We have met sub-graphs, trees, forests proved some lemmas, and saw different defintions of trees. I think that’s a good place to stop, then, that’s it for now, see you in the next one!

## One thought on “Sub-Graphs and Trees”