2.4.2. Adding Edges to a Tree

Now, if I take a tree and then I add an edge, it must create a cycle, we already saw this in this previous argument that we said, so supposing I have a tree, so a tree in general looks something like this. So, it is a graph, it has a kind of more cycles, but many things branching out. Now, if anywhere if I create a tree, supposing I add them and supposing I take some i there and some j here, we may decide to add an edge.

In a tree, which is defined as a connected acyclic graph, adding an extra edge inevitably creates a cycle. This is because a tree already connects all its vertices; if you add a new edge between any two already connected vertices, you create a situation where there are now two paths to reach between those nodes, thereby forming a cycle.

Think of a tree as a water pipe system supplying several houses without any loops. If each house is connected directly with a line and you decide to add a new line between two houses who already share a direct line, now there are two ways water can flow between those two houses, which creates a potential for redundancy or looping back – this is akin to creating a cycle in the tree.

So, another consequence of all these definitions is that between any two paths, any two vertices in a tree, there can only be one unique path. So, supposing there are actually two paths, so let us look at two vertices, here we have drawn them as i and j and suppose there are two parts. So, if I follow the two parts, then it is very clear that because there are two different ways are going there, there will be some loops somewhere in between.

There can only be one unique path between any two vertices in a tree. If there were two separate paths between two vertices, it would create a loop, contradicting the tree definition of being acyclic. Every pair of connected nodes in a tree has a single, direct route to each other without any diversions.

Consider a family tree where each person is a node. There’s only one route to understand relationships between any two family members. If Cousin A can reach Cousin B through two different ancestors, it means there’s an overlap or a loop in connections, which doesn’t align with a proper tree structure.

So, we are actually the following claim that we have these three properties, that G is connected, G is acyclic and G has n minus 1 edges, then any of these two implies the third. So, G is connected and G is acyclic by definition it is a tree, we have just shown the first arguments that any tree has n minus edges.

A tree must satisfy three main properties: it is connected, acyclic, and has exactly n-1 edges where n is the number of vertices. If you can show two of these properties, you can infer the third. This means, for example, if you prove a graph is connected and acyclic, you can conclude it must have n-1 edges.

Imagine a network of friends. If every person knows and can reach every other person (connected), and there is not a situation where a friend can know two different ways to connect to another (acyclic), then the number of relationships (edges) will be just enough to connect everyone without any unnecessary links. That is, for 5 friends, you can only have 4 unique introductions.

Now, if I take a tree and then I add an edge, it must create a cycle. Therefore, if we add an edge between any two vertices in a tree, we know that it will create a cycle. This is a significant point for understanding trees and their properties.

Adding an edge to a tree, which has n-1 edges, will result in the formation of a cycle because all vertices are already connected by definition. Thus, it reinforces that trees do not allow loops and maintains their basic structure. This understanding is crucial for designing algorithms that work with trees.

Visualize a straight road connecting several towns. Each town can only be reached in one direct route without detours. Adding a new road (edge) between any two towns that are already directly connected would mean that now there are two roads between those towns, creating a confusing circle or loop – something we want to avoid in a well-structured network.

--