Sub-Graphs and Trees

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 $G=(V,E)$ be a graph. We say that $H=(U,E^\prime)$ is a sub-graph of $G$ if:

$U\subseteq V$
$E^\prime \subseteq E \cap (U\times U)$

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

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 $H\subseteq G$ is said to be a spanning sub-graph, if $V(G)=V(H)$ . 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 $U\in V$ we will denote by $G[U]$ the spanned sub-graph on $U$ which is defined as the sub-graph with $U$ as it’s set of vertices, and the edges of it, will be all the edges between vertices in $U$ that exists in $G$ . 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 $G$ 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 $G$ 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 $G$ is a tree with two or more vertices, then it has at least two leaves. Let’s prove it:

First off all, since $G$ 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 $G$ , which we will denote by $P=(v_0,v_1,\dots ,v_l)$ (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 $v_0$ has to ‘go back’ to the longest path, i.e. it’s second endpoint is in the set $\{v_1,\dots,v_l\}$ . Why, because if it woudn’t go back to the path, we will get a longer path, which contradicts $P$ 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 $e=\{v_0,u\}$ other than $\{v_0,v_1\}$ we would have get a cycle in the graph which is a contradiction for $G$ being a tree!

Thus, $v_0$ is incident to only one edge: $\{v_0,v_1\}$ , then $d(v_0)=1$ and we found a leaf! The same process applies to $v_l$ 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 $G^\prime$ the graph spanned by the original set of vertices minus the removed leaf – $G^\prime=G[U]$ , where $U=V-\{\text{leaf}\}$ .

$G^\prime$ has no cycles, since $G$ has no cycles.
$G^\prime$ is connected: Let $u,w\in V[G^\prime]$ . There is a path between $u,w$ in $G$ . This path also appears in $G^\prime$ 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 $G^\prime$ has no cycles and is connected, thus $G^\prime$ 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 $G=(V,E)$ is a graph with $n$ vertices, the following are equiavilent:

$G$ is a tree (connected with no cycles).
$G$ is connected and $e(G)=n-1$ .
$G$ has no cycles and $e(G)=n-1$ .

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 $(1\Rightarrow 2,3)$ . We need to show that a tree has $n-1$ edges. I am going to prove it by induction.

When $n=1$ the graph is just a single vertex, thus, there are no edges at all, then $e(G)=0=1-1=n-1$ .

For some general $n$ , we will pick a leaf $v$ and remove it. By doing so, we get a new graph – $G^\prime$ , we have proved before that $G^\prime$ is also a tree, while it also has $n-1$ vertices. by induction, we know that $e(G^\prime) = (n-1) - 1 = n-2$ . Now, since $v$ is a leaf, it is incident to only one edge, thus, when removing $v$ we only ‘lose’ one edge. Therefore, $e(G)=e(G^\prime)+1=(n-2)+1=n-1$ as required.

Now, let’s prove $(2\Rightarrow 1,3)$ . Suppose that $G$ is connected with $n-1$ 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 $G^\prime$ with no cycles. $G^\prime$ is a tree with $n$ vertices, we just proved that $e(G^\prime) = n-1$ . However, $e(G) = n-1$ 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 $(3\Rightarrow 1,2)$ . $G$ has no cycles and $n-1$ edges. We need to show that it is connected.

Denote by $C_1,\dots,C_k$ the componets of $G$ . Each components is a tree (since it is connected, and the has no cycles) which is spanned by $V(C_i)$ . In other words, $G[V(C_i)]$ is a tree. Thus: $e(G[V(C_i)])=|V(C_i)| - 1$ . Overall, the number of edges in $G$ 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 $e(G) = n-1$ , thus $n-1 = n-k$ and we get that $k = 1$ . 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!

Sub-Graphs

Forest & Trees – The graphs

Summary

Like this:

One thought on “Sub-Graphs and Trees”

Leave a Reply Cancel reply

Sub-Graphs

Forest & Trees – The graphs

Summary

Share

Like this:

One thought on “Sub-Graphs and Trees”

Leave a Reply Cancel reply